1

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

通过递归，我试图探索所有节点，直到找到我正在寻找的节点，然后返回并将级联返回返回到函数调用堆栈的顶部，同时将总成本加起来。

性能并不重要，但如果使用递归使其变得比需要的困难得多，我愿意重写我的代码。

4

1 回答 1

10

Dijkstra 的算法不是递归的。递归算法最终将是深度优先的，而 Dijkstra 的算法是广度优先搜索。

中心思想是你有一个未访问节点的优先级队列。每次迭代都将距离最短的节点拉离队列的前端并访问它。然后更新到每个未访问邻居的距离。

像这样的基于队列的算法不适合递归实现。搜索不会像深度优先搜索那样在尝试替代路径之前探索一条耗尽路径。它同时探索许多路径，只要它们是最便宜的路径就探索它们。一旦当前路径不再是最便宜的，它就会转移到另一条路径。递归不会让你从一个路径“跳跃”到另一个路径。

您可以在Wikipedia 文章的图形中看到这种行为。

在此处输入图像描述

于 2013-04-18T03:51:53.877 回答