c++ - 将递归更改为更便宜的东西

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到我用来解决这个问题的代码 question