我正在尝试用 C++ 编写 Dijkstra 算法,互联网上有无数示例,但我似乎无法理解这些示例是如何工作的。我宁愿以一种对我有意义的方式来做,这样我就能更好地理解算法。我知道算法本身应该如何工作,并且我已经编写了一些代码。我想知道是否有人可以指出我思维过程中的缺陷。我选择将我的图形表示为边缘列表。我将用伪代码编写,因为我的实际代码一团糟:
class Node{
vector<node> linkVector; //links to other nodes, generated at random
int cost; //randomly generated by constructor
bool visited = false;
}
vector<node> edgelist; //contains all nodes
int main(){
create n Nodes
add all nodes to edgeList
for each node {
randomly add WEIGHT nodes to linkVector
}
findPath(initialNode)
}
int findPath(Node start, node want, int cost=0){ //returns cost from src to dest
if(start==want) return cost;
if(every node has been visited) return 0; //this is in case of failure
Node result = getMinimumCost() //finds node in linkVector with least cost
result.visited(true) //so we don't get stuck in a loop
findPath(result, want, result.getCost() + cost); //recursive call
}
通过递归,我试图探索所有节点,直到找到我正在寻找的节点,然后返回并利用级联返回返回到函数调用堆栈的顶部,同时将总成本。
性能并不重要,但如果使用递归使它比需要的更难,我愿意重写我的代码。
最佳答案
Dijkstra 算法不是递归的。递归算法最终会是深度优先的,而 Dijkstra 的算法是广度优先搜索。
中心思想是您有一个未访问节点的优先级队列。每次迭代,您将距离最短的节点拉出队列前端并访问它。然后更新到每个未访问邻居的距离。
诸如此类的基于队列的算法不适合递归实现。在尝试替代路径之前,搜索不会像深度优先搜索那样探索一条穷尽路径。它同时探索多条路径,只探索成本最低的路径。一旦当前路径不再是最便宜的,它就会转到另一条路径。递归不允许您从一条路径“跳”到另一条路径。
您可以在 Wikipedia article 的图形中看到此行为.
关于c++ - Dijkstra 算法伪代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16074083/