Dijkstra的最短路径算法 [英] Dijkstra’s shortest path algorithm

问题描述

下面是我的教授给我们的算法总结。

什么是图中的一个节点，作为第3步中提到的家长？的我有点困惑，因为我虽然该节点只有邻居，没有父母？

我的第二个问题是关于第3步，拿起index个纪录在堆栈中。由于栈只允许您查看上面，我不知道的这是什么意思拿起index个纪录？的

Dijkstra的最短路径：

  0步：如果s = D，停下来。
步骤1：当前节点C = S，c.length = 0，stack.push（三，它的长度和父）。
        如果u是源S则不需要父母。
第2步：分= 0，跳=无限，指数= 1
第3步：拿起index个纪录栈，说节点u，其长度u.length，
        与其父瓦特
第4步：找铀的邻居表中的邻居，讲诉，使得v是
        在堆栈和＆lt任何项目未找到; U，V＆GT; + u.length＆LT;跳。
第5步：如果这样的邻居发现，跳=分钟= u.length + LT; U，V＆GT;和record_node = V
第6步：转到第4步直到你的所有邻居都试过（全部可
        在栈中找到）。
步骤7：指数++，转到步骤3，直到所有的节点都试过了（在发现
        堆栈）。
第8步：C = record_node，c.length =分钟，stack_push（C，c.length，U）。如果C = D
        停止整个过程，并进行到步骤9的数据收集，
        否则，转到步骤2。
步骤9：（吨，d.length，和t.parent）=（D，d.length，和d.parent）堆栈，
        继续搜索上（t.parent，t.parent.length，t.parent.parent）
        直到t.parent = S。
 

解决方案

在一个图，节点只有邻居，但在运行Dijkstra算法您建立一个树描述了在所有节点从开始节点的最短路径原始图

在算法运行的开始，所有节点都有其predecessor节点设置为空，并在每个迭代一个父被设定为导致最短路径的节点。

有一个在此的Dijkstra算法可视化并注意算法的结果，实际上是图的子树

希望这能回答你的问题：）

The following is algorithm summary given to us by our professor.

What is the parent of a node in a graph as referred to in step 3? I'm a little confused as I though that the nodes only had neighbors and doesn't have a parent?

My second question is about step 3, "pick up the index’th record in stack." Since a stack only allows you to view the top, I'm not sure what it means by picking up the index'th record?

Dijkstra’s shortest path:

Step 0: if s == d, stop.
Step 1: current node c= s, c.length = 0, stack.push (c, its length, and parent). 
        If u is the source s then no need for parent.
Step 2: min = 0, hop = infinite, index = 1
Step 3: pick up the index’th record in stack, say node u, its length u.length, 
        and its parent w.
Step 4: find a neighbor of u in the table of neighbors, say v, such that v is 
        not found in any item in stack and <u,v> +u.length< hop. 
Step 5: if such a neighbor is found, hop=min=u.length + <u,v> and record_node = v
Step 6: go to step 4 until all the neighbors of u have been tried (all can be 
        found in stack).
Step 7: index ++, go to step 3 until all the nodes have been tried (found in 
        stack).
Step 8: c = record_node, c.length = min, stack_push(c, c.length, u). If c == d 
        stop the entire process and goes to step 9 for data collection, 
        otherwise go to step 2.
Step 9: (t, d.length, and t.parent) = (d, d.length, and d.parent) in stack, 
        keep searching on (t.parent, t.parent.length, t.parent.parent), 
        until t.parent = s.

解决方案

In a graph, nodes only have neighbors, but while running Dijkstra's algorithm you build a "tree" describing the shortest path from the starting node to all the nodes in the original graph.

at the beginning of the algorithm run, all the nodes have their predecessor node set to null, and on each iteration a parent is set to the node leading to the shortest path.

Have a look at this Visualization of Dijkstra's Algorithm and notice that the result of the algorithm is in fact a sub-tree of the graph.

Hope that answers your question :)

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