证明path[j]=u假设→a→u是v到j的最短路径但不是v到u的最短路径vaupath[j]=u该路径更短，与假设矛盾！11/46
v u j path[j]=u a 假设 v → a → u → j 是v到j的最短路径 但 v → a → u 不是v到u的最短路径 v u j path[j]=u b a 该路径更短，与假设矛盾！ 11/46
path表示path[v]=-1path[u]=wpath[j]=upath[w]=v由path反推最短路径path[j]=u逆路径：juwvpath[u]=w反向：→w→→jpath[w]=v（到源点为止）12/46
v u j path[j]=u w path[v]=-1 path[w]=v path[u]=w path[j]=u path[u]=w path[w]=v（到源点为止） 逆路径：j u w v 反向：v → w → u → j 12/46
6U.6示例43F5SUdist[]path[]Y340O17(0][1,2,3,4,5,6][0,4.6O001-1.-11AO最小的顶点：1[0,1](2,3,4,5,6][0, 4, 5. 6, 11, 8, ∞] [0, 0, 1, 0,1,-1,-1}最小的顶点：2[0,1,2](3,4,5,6]2, -1){0, 4, 5, 6, 11. 9. ∞} {0, 0, 1, 0, 1,13/46
示例 0 1 3 2 4 5 6 4 6 1 6 8 5 6 6 2 4 1 7 S U dist[] path[] 0 1 2 3 4 5 6 0 1 2 3 4 5 6 {0} {1,2,3,4,5,6} {0, 4, 6, 6, ∞, ∞, ∞} {0, 0, 0, 0, -1, -1, -1} {0,1} {2,3,4,5,6} {0, 4, 5, 6, 11, ∞, ∞} {0, 0, 1, 0, 1, -1, -1} {0,1,2} {3,4,5,6} {0, 4, 5, 6, 11, 9, ∞} {0, 0, 1, 0, 1, 2, -1} 最小的顶点：1 最小的顶点：2 13/46
669D3Udist[]Spath[]34160115[0,1,2][3,4,5,6](0,5,6.11.9.10,911.9最小的顶点：3[4,5,6][0,1,2,3][o,4, 5, 6, 11, 9, α){0, 0, 1, 0,1.2,-1最小的顶点：5[4,6][0,1,2,3,5][0, 4,5, 6,1,9,_17]5.5110.0.1.0.2.14/46
S U dist[] path[] 0 1 2 3 4 5 6 0 1 2 3 4 5 6 {0,1,2} {3,4,5,6} {0, 4, 5, 6, 11, 9, ∞} {0, 0, 1, 0, 1, 2, -1} 最小的顶点：3 {0,1,2,3} {4,5,6} {0, 4, 5, 6, 11, 9, ∞} {0, 0, 1, 0, 1, 2, -1} 最小的顶点：5 {0,1,2,3,5} {4,6} {0, 4, 5, 6, 10, 9, 17} {0, 0, 1, 0, 5, 2, 5} 0 1 3 2 4 5 6 4 6 1 6 8 5 6 6 2 4 1 7 14/46
U.4dist[]Upath[]342C-[4,6][0,1,2,3,5](o,17)100.54最小的顶点：(6][0,1,2,3,5,4](0,4, 5, 6,10, 9, 161[0, 0, 1,最小的顶点：[0,1,2,3,5,4,6](0,4,5,6,10,9,16){0, 0, 1, 0,54最终结果15/46
S U dist[] path[] 0 1 2 3 4 5 6 0 1 2 3 4 5 6 最小的顶点：4 {0,1,2,3,5} {4,6} {0, 4, 5, 6, 10, 9, 17} {0, 0, 1, 0, 5, 2, 5} {0,1,2,3,5,4} {6} {0, 4, 5, 6, 10, 9, 16} {0, 0, 1, 0, 5, 2, 4} 最小的顶点：6 {0,1,2,3,5,4,6} {} {0, 4, 5, 6, 10, 9, 16} {0, 0, 1, 0, 5, 2, 4} 最终结果 0 1 3 2 4 5 6 4 6 1 6 8 5 6 6 2 4 1 7 15/46