Dijkstra的算法伪码 [英] Dijkstra's algorithm pseudocode

问题描述

我想用C ++编写Dijkstra的算法，在互联网上有无数的例子，但我只是不能理解示例如何工作。我宁愿这样做对我有意义，所以我可以更好地理解算法。我知道算法本身应该如何工作，我已经写了一些代码。我想知道是否有人可以指出我的思维过程中的缺陷。我选择将我的图表表示为边列表。我将写入伪代码，因为我的实际代码是一个巨大的混乱：

I'm trying to write Dijkstra's algorithm in C++, and there are countless examples on the internet but I just can't seem to grasp how the examples work. I'd rather do it in a way that makes sense to me so I can understand the algorithm better. I know how the algorithm itself should work, and I have written some code. I was wondering if someone could point out the flaw in my thought process. I'm choosing to represent my graph as an edge list. I'll write in pseudocode because my actual code is a huge mess:

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
}

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

Via recursion, I'm trying to explore all the nodes until I find the one I'm looking for, then return and ride the cascading returns back up to the top of the function call stack, all the while adding up the total cost.

性能并不重要，但如果使用递归使它比它需要的更难，我可以重写我的代码。

Performance doesn't really matter, but if using recursion makes it much harder than it needs to be, I am open to rewriting my code.

推荐答案

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

Dijkstra's algorithm isn't recursive. A recursive algorithm would end up being depth-first whereas Dijkstra's algorithm is a breadth-first search.

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

The central idea is that you have a priority queue of unvisited nodes. Each iteration you pull the node with the shortest distance off of the front of the queue and visit it. Then you update the distances to each of its unvisited neighbors.

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

A queue-based algorithm such as this does not lend itself to a recursive implementation. The search does not explore one path to exhaustion before it tries an alternate path as a depth-first search would do. It explores many paths simultaneously, only exploring them as long as they are the cheapest path. As soon as the current path is no longer the cheapest it moves on to another path. Recursion doesn't let you "jump" from path to path.

您可以从维基百科文章。

这篇关于Dijkstra的算法伪码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！