以下是我们教授给我们的算法总结。
第 3 步中提到的图中节点的父节点是什么？ 我有点困惑，因为我认为节点只有邻居而没有父节点？
我的第二个问题是关于第 3 步，“在堆栈中取出索引的第一个记录”。由于堆栈只允许您查看顶部，我不确定拾取索引的第记录是什么意思？
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.
最佳答案
在图中，节点只有邻居，但在运行 Dijkstra 算法时，您构建了一个“树”，描述了从起始节点到原始图中所有节点的最短路径。
在算法运行开始时，所有节点都将其前任节点设置为空，并且在每次迭代中将父节点设置为通向最短路径的节点。
看看这个Visualization of Dijkstra's Algorithm并注意算法的结果实际上是图的子树。
希望这能回答您的问题:)
关于algorithm - Dijkstra 最短路径算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8329133/