Dijkstra算法伪code [英] Dijkstra's algorithm pseudocode

问题描述

我想写Dijkstra算法在C ++，并有在互联网上无数的例子，但我似乎无法把握的例子是如何工作的。我宁愿做的方式，对我来说很有意义，所以我可以理解算法更好。我知道算法本身应该如何工作的，我已经写了一些code。我想知道，如果有人能指出该缺陷在我的思维过程。我选择重新present我的曲线图，作为一个边列表。我会写在伪code，因为我的实际code是一个巨大的烂摊子：

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.

性能并不重要，但如果使用递归使得它更难比它需要，我愿意重写我的code。

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.

您可以看到从维基百科的文章图形这种行为。

You can see this behavior in the graphic from the Wikipedia article.

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