解读 Dijkstra 算法
Interpreting Dijkstra's Algorithm
我明白如何按照Dijkstra算法的解释从头到尾找到最短路径，我不明白的是解释。在这里，从图中的图形来看，从 A 到 E 添加到我已知集合的顺序是 A,C,B,D,F,H,G,E 我没有得到的是，如何获得如图所示的从 A 到 E 的路径（数学方面)
每个节点都有一个父节点。当您到达 'E' 时，您只需查看其父项，依此类推，直到找到 'A'。这样，您将以相反的顺序找到列表。反转列表以找到从 'A' 到 'E' 的路径。
如果您按顺序追加，您的父级列表将是 'E' 'G' 'H' 'F' 'B' 'A'。
注意："parent node" 是 table 的 "path" 列中指示的节点
考虑包含要遍历的路径的最小优先级队列，其中路径在队列上的优先级是遍历路径中从根到并包括该边的边的成本。在算法的每一步中，从队列中弹出成本最低的路径，并考虑其每个事件边缘，扩展具有该事件边缘的路径，并将新路径按优先顺序推回队列。重复直到第一条路径到达目的地。
例如：
- 从空队列开始
<>
- 然后，从根
A开始，将所有事件边（A->B、A->C和A->D的成本分别为2、1和4）放入队列和优先顺序：<(A->C,1),(A->B,2),(A->D,4)>
- 从队列的前面弹出优先级最低的路径
A->C，然后考虑入射到路径末尾的边C并将这些路径推回队列（保持优先级订单）：<(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)>
- 重复，弹出最小优先级路径
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)>
- 继续...弹出
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)>
- 弹出
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)>
- pop
A->D->C - 但是，我们已经到达 C 且成本较低的路径，因此可以忽略它。
- 弹出
A->B->C 并忽略它。
- 弹出
A->B->F->H 并推入更多事件边：<(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
- 弹出
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)>
- 弹出
A->B->F->H->G->F 并忽略它。
- 弹出
A->C->A 并忽略它。
- pop
A->B->F->H->G->E 我们已经达到了目标（成本为 11）！
从起始节点开始，遍历图到可用节点时进行累积权重计算。从一个节点到相邻节点的累积权重与任何先前的结果（即，对该节点的可能遍历）进行比较。然后选择累积权重最低的路线作为"winner"。重复该过程，直到找到从起始节点到终端节点的路径并评估为最低累积权重。
因此在您展示的示例中：
- ACE = 12
- ADCE = 17
- 安倍 = 12
ABFHGE 是唯一剩下的（在有向图中）从开始到结束累积权重最低为 11（也是最长的路径）的路径。
当您从一开始计算时，一些路径最初可能看起来更短 (AC)，但随着算法的进展，这些选择将被放弃，因为从 A 到 E 的所有路径都被探索过。
我明白如何按照Dijkstra算法的解释从头到尾找到最短路径，我不明白的是解释。在这里，从图中的图形来看，从 A 到 E 添加到我已知集合的顺序是 A,C,B,D,F,H,G,E 我没有得到的是，如何获得如图所示的从 A 到 E 的路径（数学方面)
每个节点都有一个父节点。当您到达 'E' 时，您只需查看其父项，依此类推，直到找到 'A'。这样，您将以相反的顺序找到列表。反转列表以找到从 'A' 到 'E' 的路径。
如果您按顺序追加，您的父级列表将是 'E' 'G' 'H' 'F' 'B' 'A'。
注意："parent node" 是 table 的 "path" 列中指示的节点
考虑包含要遍历的路径的最小优先级队列，其中路径在队列上的优先级是遍历路径中从根到并包括该边的边的成本。在算法的每一步中，从队列中弹出成本最低的路径，并考虑其每个事件边缘，扩展具有该事件边缘的路径，并将新路径按优先顺序推回队列。重复直到第一条路径到达目的地。
例如：
- 从空队列开始
<> - 然后，从根
A开始，将所有事件边（A->B、A->C和A->D的成本分别为2、1和4）放入队列和优先顺序：<(A->C,1),(A->B,2),(A->D,4)> - 从队列的前面弹出优先级最低的路径
A->C，然后考虑入射到路径末尾的边C并将这些路径推回队列（保持优先级订单）：<(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)> - 重复，弹出最小优先级路径
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)> - 继续...弹出
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)> - 弹出
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)> - pop
A->D->C- 但是，我们已经到达C且成本较低的路径，因此可以忽略它。 - 弹出
A->B->C并忽略它。 - 弹出
A->B->F->H并推入更多事件边：<(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)> - 弹出
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)> - 弹出
A->B->F->H->G->F并忽略它。 - 弹出
A->C->A并忽略它。 - pop
A->B->F->H->G->E我们已经达到了目标（成本为 11）！
从起始节点开始，遍历图到可用节点时进行累积权重计算。从一个节点到相邻节点的累积权重与任何先前的结果（即，对该节点的可能遍历）进行比较。然后选择累积权重最低的路线作为"winner"。重复该过程，直到找到从起始节点到终端节点的路径并评估为最低累积权重。
因此在您展示的示例中：
- ACE = 12
- ADCE = 17
- 安倍 = 12
ABFHGE 是唯一剩下的（在有向图中）从开始到结束累积权重最低为 11（也是最长的路径）的路径。
当您从一开始计算时，一些路径最初可能看起来更短 (AC)，但随着算法的进展，这些选择将被放弃，因为从 A 到 E 的所有路径都被探索过。