目录
Dijkstra 算法
以下面有向图为例：
graph LR V0((V0)) -- 10 --> V1((V1)) V0((V0)) -- 5 --> V4((V4)) V1((V1)) -- 2 --> V4((V4)) V4((V4)) -- 3 --> V1((V1)) V1((V1)) -- 1 --> V2((V2)) V4((V4)) -- 9 --> V2((V2)) V4((V4)) -- 2 --> V3((V3)) V3((V3)) -- 7 --> V0((V0)) V3((V3)) -- 6 --> V2((V2)) V2((V2)) -- 4 --> V3((V3))step0. 初始状态
- final 数组：标记各顶点是否已找到最短路径
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| True | False | False | False | False |
- dist 数组：记录从源点（V0）到该点（Vi）的最短路径长度
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 0 | 10 | ∞ | ∞ | 5 |
- path 数组：路径上的前驱（前面的结点）
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| -1 | 0 | -1 | -1 | 0 |
step1. 第一轮
【1】找到 step0 中 ：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V4，令 final[i] = True。
- final 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| True | False | False | False | True |
【2】检查所有邻接自 Vi = V4 的点，若其 final 值为 False，则对比 step0 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。
对于 V1（原本 dist = 10， path = 0）：final 值为 False，从 V0-->V4-->V1 的路径长度为 5+3=8<10，所以需要更新其 dist =8，path = 4；
对于 V2（原本 dist = ∞， path = -1）：final 值为 False，从 V0-->V4-->V2 的路径长度为 5+9=14<∞，所以需要更新其 dist =14，path = 4；
对于 V3（原本 dist = ∞， path = -1）：final 值为 False，从 V0-->V4-->V3 的路径长度为 5+2=7<∞，所以需要更新其 dist =7，path = 4。
- dist 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 0 | 8 | 14 | 7 | 5 |
- path 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| -1 | 4 | 4 | 4 | 0 |
step2. 第二轮
【1】找到 step1 中 ：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V3，令 final[i] = True。
- final 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| True | False | False | True | True |
【2】检查所有邻接自 Vi = V3 的点（对应 dist = 7，path = 4），若其 final 值为 False，则对比 step1 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。
对于 V0：final 值为 True。
对于 V2（原本 dist = 14，path = 4）：final 值为 False，从 V0-->V4-->V3-->V2 的路径长度为 7+6=13<14，所以需要更新其 dist =13，path = 3。
- dist 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 0 | 8 | 13 | 7 | 5 |
- path 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| -1 | 4 | 3 | 4 | 0 |
step3. 第三轮
【1】找到 step2 中 ：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V1，令 final[i] = True。
- final 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| True | True | False | True | True |
【2】检查所有邻接自 Vi = V1 的点（对应 dist = 8，path = 4），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。
对于 V2（原本 dist = 13，path = 3）：final 值为 False，从 V0-->V4-->V1-->V2 的路径长度为 8+1=9<13，所以需要更新其 dist =9，path = 1。
对于 V4：final 值为 True。
- dist 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 0 | 8 | 9 | 7 | 5 |
- path 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| -1 | 4 | 1 | 4 | 0 |
step4. 第四轮
【1】找到 step2 中 ：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V2，令 final[i] = True。
- final 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| True | True | True | True | True |
【2】检查所有邻接自 Vi = V2 的点（对应 dist = 9，path = 1），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。
已经找不到其他未访问结点，算法结束，以下为最终结果：
- dist 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| 0 | 8 | 9 | 7 | 5 |
- path 数组：
| V0 | V1 | V2 | V3 | V4 |
|---|---|---|---|---|
| -1 | 4 | 1 | 4 | 0 |