迪杰斯特拉最短路径算法

Question

以下是我们教授给出的算法摘要。

在步骤3中，“父节点”指的是图中节点的上一级。可能会有些困惑，因为节点通常只有邻居而没有父节点。

我的第二个问题与步骤3有关，“从堆栈中选择第index个记录”。由于堆栈只允许您查看顶部，所以我不确定“选择第index个记录”是什么意思。

Dijkstra最短路径算法：

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.

- Claire Klein

---

你有没有尝试跟你的教授讨论这些问题？由于他给了你这个算法，他可能会最清楚地解释它。 - Dan W

是的，我已经询问过了。不幸的是，存在语言障碍导致了问题。我希望有人能够深刻理解该算法，并能识别出他想要表达的内容。谢谢。 - Claire Klein

这很可怕（指摘要）。请在维基百科或类似来源上了解该算法，那里的描述不会这么密集。如果有良好的解释，算法本身并不难理解。 - user1046334

你看过这里了吗？http://en.wikipedia.org/wiki/Dijkstra's_algorithm - Robert Harvey

Answer 1

在一个图中，节点只有邻居，但是在运行Dijkstra算法时，您会构建一棵描述从起始节点到原始图中所有节点的最短路径的“树”。

在算法运行开始时，所有节点的前任节点都设置为null，在每次迭代中，父节点被设置为通向最短路径的节点。

请查看这个Dijkstra算法可视化，注意算法的结果实际上是图的一个子树。

希望这回答了您的问题 :)

- Ido.Co

Answer 2

也许这个小程序可以帮助你。

我强烈建议在互联网上寻找更好的算法解释。这是目前导航软件中最常用的算法，每个主要的导航公司都在使用它（可能还有小公司）。它也被用作游戏中的路径规划算法。

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/dijkstra.html

- Tom van der Woerdt

Answer 3

Parent是指在您当前正在检查的节点之前一步路径上的节点。换句话说：路径是一个有向图，每个节点都有2个顺序（即，它由边连接到另外两个节点），除了第一个和最后一个节点。节点的父节点是该节点的前任。

关于堆栈：可能这不是一个真正的堆栈，只是一个您可以将节点推入其中的结构；然后您可以在此结构上索引所有节点，而不仅仅是顶部的节点。但我同意，堆栈不是一个好的选择。

- mort