Dijkstra的算法伪代码

Question

我正在尝试用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
}

通过递归,我试图探索所有节点,直到找到我正在寻找的那个节点,然后返回并将级联返回乘坐到函数调用堆栈的顶部,同时累计总成本.

性能并不重要,但如果使用递归使得它比它需要的更难,我愿意重写我的代码.

Answer 1

Dijkstra的算法不是递归的.递归算法最终将成为深度优先,而Dijkstra算法则是广度优先搜索.

中心思想是您拥有未访问节点的优先级队列.每次迭代都会以最短距离拉出节点并离开队列并访问它.然后,您更新每个未访问的邻居的距离.

诸如此类的基于队列的算法不适合递归实现.在尝试使用深度优先搜索的备用路径之前,搜索不会探索一条耗尽的路径.它同时探索了许多路径,只要探索它们,只要它们是最便宜的路径.一旦当前路径不再是最便宜的,它就会移动到另一条路径上.递归不会让你从路径"跳"到路径.

您可以在Wikipedia文章的图形中看到此行为.