解释Dijkstra算法

Question

​

​

正如Dijkstra算法所解释的那样，我理解如何找到从头到尾的最短路径，但我不明白的是解释。在这里，从图中添加到我的已知集从A到E是A,C,B,D,F,H,G,E，我没有得到的是，如何得到从A到E的路径，如图中所示(数学方面)

Answer 1

每个节点都有一个父节点。当您到达'E'时，只需查看它的父级等等，直到找到'A'为止。这样你就能找到顺序相反的列表了。反转列表以找到从'A'到'E'的路径。

如果按顺序追加，则父列表将为'E' 'G' 'H' 'F' 'B' 'A'。

注意：“父节点”是表的“路径”列中指示的节点

Answer 2

考虑包含要遍历的路径的最小优先级队列，其中路径在队列上的优先级是从根到包含该边缘遍历路径中的边的成本。在算法的每一步，从队列中弹出代价最低的路径，并考虑其每一个事件边缘，用该事件边缘扩展路径，并按优先级顺序将新路径推回队列。重复，直到第一条路径到达目的地。

例如：

1. 从空队列<>开始
2. 然后，从根A开始，将所有事件边缘(分别为代价2、1和4的A->B、A->C和A->D )放入队列并按优先级排序：<(A->C,1),(A->B,2),(A->D,4)>。
3. 从队列前面弹出最小优先级路径A->C，然后考虑与路径C相关的边缘，并将这些路径推回队列(保持优先级顺序)：<(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)>
4. 重复，弹出最小优先级路径A->B关闭并扩展具有事件边缘的路径：<(A->D,4),(A->B->F,4),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
5. 继续走..。弹出A->D并推送更多事件边缘：<(A->B->F,4),(A->D->C,6),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
6. 弹出A->B->F并推送更多事件边缘：<(A->D->C,6),(A->B->C,7),(A->B->F->H,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
7. pop A->D->C --然而，我们已经以较低的成本达到了C，因此可以忽略它。
8. 弹出A->B->C并忽略它。
9. 弹出A->B->F->H并推送更多事件边缘：<(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
10. 弹出A->B->F->H并推送更多事件边缘：<(A->B->F->H->G->F,10),(A->C->A,10),(A->B->F->H->G->E,11),(A->B->E,12),(A->C->E,12)>
11. 弹出A->B->F->H->G->F并忽略它。
12. 弹出A->C->A并忽略它。
13. pop A->B->F->H->G->E和我们已经达到了目标(花费11)！

Answer 3

从开始节点开始，在遍历图到可用节点时进行累积权重计算。将从一个节点到相邻节点的累积权重与任何先前的结果(即可能的遍历到该节点)进行比较。然后选择累积重量最低的路线作为“赢家”。该过程重复，直到从开始到终端节点的路径被找到，并被评估为最低的累积权重。

因此，在这个例子中，您已经展示了：

• ACE = 12
• ADCE = 17
• 安倍= 12

ABFHGE是唯一剩下的路径(在有向图中)，从开始到结束的最小累积权重为11 (也是最长的路径)。

当您从一开始计算时，一些路径可能最初看起来更短(AC)，但是随着算法的进展，这些选择将被放弃，因为从A到E的所有路径都会被探索。