题目
有向图如下所示，试用迪杰斯特拉算法求出顶点a到其他各顶点间的最短路径。
算法过程
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | |
| b | 15(a,b) | 15(a,b) | 15(a,b) | 15(a,b) | 15(a,b) | 15(a,b) |
| c | 2(a,c) | |||||
| d | 12(a,d) | 12(a,d) | 11(a,c,f,d) | 11(a,c,f,d) | ||
| e | 无限 | 10(a,c,e) | 10(a,c,e) | |||
| f | 无限 | 6(a,c,f) | ||||
| g | 无限 | 15(a,d,g) | 15(a,d,g) | 15(a,d,g) | 14(a,c,f,d,g) | |
| s | {a,c} | {a,c,f} | {a,c,e} | {a,c,f,d} | {a,c,f,d,g} | {a,b} |
s为终点集，b、c、d、e、f、g为终点。
邻接矩阵
| a | b | c | d | e | f | g | |
| a | 0 | 15 | 2 | 12 | INF | INF | INF |
| b | INF | 0 | INF | INF | 6 | INF | INF |
| c | INF | INF | 0 | INF | 8 | 4 | INF |
| d | INF | INF | INF | 0 | INF | INF | 3 |
| e | INF | INF | INF | INF | 0 | INF | 9 |
| f | INF | INF | INF | 5 | INF | 0 | 10 |
| g | INF | 4 | INF | INF | INF | INF | 0 |
INF为无限符号（∞）代替
版权声明：本文为m0_58138734原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。