将递归更改为更便宜的东西

Question

我正在尝试找到从顶点到另一个顶点的最短路径。更准确地说，我有一个有向图，并且通过始终在其中“前进”，我将永远结束。类似于神经网络的结构。我决定找到最短的递归方式，它在较小的数字下工作得很好。但是对于更大的数据，我得到了 SIGSEGV。我几乎可以肯定这是堆栈溢出。你们中有人知道我如何从简单的循环切换到不会造成麻烦的东西吗？

int findShortestPath(Vertex * v, int endPointX){
    if(v->isShortestPathSet())
        return v->getShortestPath();
    vector<int> * paths = new vector<int>;
    if(v->getEndPos() == endPointX)
        return 0;
    for(int i = 0; i < v->getOutputEdges().size(); i ++){
        Edge * outputEdge = v->getOutputEdges().at(i);
        paths->push_back(findShortestPath(outputEdge->getOutputVertex(), endPointX) + outputEdge->getValue());
    }
    int minPath = paths->at(0);
    for(int i = 0; i < paths->size(); i ++){
        if(paths->at(i) < minPath)
            minPath = paths->at(i);
    }
    v->setShortestPath(minPath);
    free(paths);
    return minPath;
}

这是我用来寻找最短路径的函数。它记录了到每个顶点的最短可能路径，因此在进一步的查询中我不必重复这些昂贵的计算。

Answer 1

您可以迭代地实现 Dijkstra 算法。这是迭代地实现 Dijkstra 算法的代码片段

#include <queue>
#include <unordered_map>
#include <vector>

using IntPair = std::pair<int,int>;
std::priority_queue<IntPair, std::vector<IntPair>, std::greater<IntPair>> pq;
std::unordered_map<int, std::unordered_map<int, int>> g;
std::vector<int> distance, parent;

void dijkstras(int startVertex) {
    // insert the startVertex into the priority queue(pq)
    pq.push(std::make_pair(0, startVertex));

    while (!pq.empty()) {
        // select the vertex with least distance travelled so far from the pq
        // and then, pop the selected vertex from pq
        auto [dist, src] = pq.top(); pq.pop();
        // iterate on all its neighbours and update distance[] and parent[]
        for (auto [v, weight] : g[src]) {
            if (int newDist = dist + weight; newDist < distance[v]) {
                parent[v] = src;
                distance[v] = newDist;
                pq.push(std::make_pair(newDist, v));
            }
        }
    }
}

这里，

pq 是一个优先级队列，它存储 (distanceTravelledSoFar, previousNode) 对。在这里，pq 充当最小堆，帮助我们最佳地选择下一个节点
g只是一个用来存储图的邻接表
distance 是从 startVertex
parent是存放从startVertex

这是link to the code which I have used to solve this question

Answer 2

您的问题的答案在评论中给出了建议（Cherubim 给出了 Dijkstra's algoritm 的一个很好的例子。

我也会通过修改你的代码来回答。首先，我认为 getter 和 setter 不是必需的，您应该使用现代 C++。因此我修改了你的代码如下：

#include <vector>
#include <algorithm>
#include <optional>

class Vertex;

struct Edge {
    Vertex* const outputVertex;
    int const value;
};

struct Vertex {
    int const endPoint;
    std::vector<Edge const*> const outputEdges;
    std::optional<int> shortestPath;
};

int findShortestPath(Vertex* const v, int endPoint){
    if(v->endPoint == endPoint) return 0;
    if(v->shortestPath.has_value()) return v->shortestPath.value();
    auto const& outputEdges = v->outputEdges; // hopefully prevent one layer of indirection
    std::vector<int> paths; paths.reserve(outputEdges.size());
    std::transform(cbegin(outputEdges), cend(outputEdges), back_inserter(paths),
       [endPoint] (Edge const* const outputEdge) { 
           return findShortestPath(outputEdge->outputVertex, endPoint) + outputEdge->value;
            });
    return v->shortestPath.value() = *std::min_element(cbegin(paths), cend(paths));
}

现在，要实现堆栈，您必须颠倒您正在使用的概念：不是递归到深度并返回距离，而是向前传递距离。与评论中建议的堆栈一起，这将导致以下代码：

#include <stack>
#include <utility>
#include <climits>

int findShortestPath(Vertex const* const startVertexPtr, int endPoint) {
    int minDistance = INT_MAX;
    std::stack<std::pair<Vertex const*, int>> s;
    s.push(std::make_pair(startVertexPtr, 0));
    while(!s.empty()) {
        auto [vertexPtr, distance] = s.top(); s.pop(); // structured binding
        if (vertexPtr->endPoint == endPoint) {
            minDistance = std::min(minDistance, distance); // end is found, see if it's path has minimum distance
            continue;
        }
        for(Edge const* const edge : vertexPtr->outputEdges) {
            s.push(std::make_pair(edge->outputVertex, distance + edge->value)); // pass the distance forward
        }
    }
    return minDistance;
}

...但是你看我在这里没有使用 Vertex::shortestPath，这会提供优化。我还没有完全检查过，但你可以这样做：首先我再次重新定义 Vertex

struct Vertex {
    int const endPoint;
    std::vector<Edge const*> const outputEdges;
    int shortestPath = INT_MAX;
};

然后：

int findShortestPath(Vertex const* const startVertexPtr, int endPoint) {
    int minDistance = INT_MAX;
    std::stack<std::pair<Vertex const*, int>> s;
    s.push(std::make_pair(startVertexPtr, 0));
    while(!s.empty()) {
        auto [vertexPtr, distance] = s.top(); s.pop();
        if (vertexPtr->endPoint == endPoint) {
            minDistance = std::min(minDistance, distance);
            continue;
        }
        for(Edge const* const edge : vertexPtr->outputEdges) {
            Vertex& vertex = *edge->outputVertex; // hopefully one less level of indirection
            auto newDistance = distance + edge->value;
            if (newDistance < vertex.shortestPath) {
                vertex.shortestPath = newDistance;
                s.push(std::make_pair(&vertex, newDistance));
            }
        }
    }
    return minDistance;
}

但可能还有更多优化的可能。

将递归更改为更便宜的东西

Change recursion to something less expensive

c++

graph-theory

dijkstra