Dijkstra算法 迪杰斯特拉算法 单源最短路径
写在前边的话：写作不易，有帮助到你的话麻烦点赞加收藏呦。感激不尽！如有错误也请留言指正
【东南大学2000四(10分)】试利用Dijkstra算法求下图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。
Round1
在第一轮中，填入b、c、d、e、f、g与a之间的距离，然后选出最短距离，并在下方标注路径
| Round1 | Round2 | Round3 | Round4 | Round5 | Round6 | |
| b | 15 |
|
||||
| c | 2 a-c |
|||||
| d | 12 |
|
||||
| e | ∞ |
|
||||
| f | ∞ |
|
||||
| g | ∞ |
|
||||
| 集合S | c |
Round2
由于我们在第一轮选择出来了距离a点最近的c点，所以在填第二轮的时候，其余的点如果通过c点可以使得距离变得更短，那么更新该点的值，并更新路径。以d点为例，在round1中，距离为∞，可是通过c点距离就变为了10，我们更新d点距离，并且更新路径。
| Round1 | Round2 | Round3 | Round4 | Round5 | Round6 | |
|---|---|---|---|---|---|---|
| b | 15 | 15 |
|
|||
| c | 2 a-c |
|||||
| d | 12 | 12 |
|
|||
| e | ∞ | 10 a-c-e |
||||
| f | ∞ | 6 a-c-f |
||||
| g | ∞ | ∞ |
|
|||
| 集合S | c | cf |
Round3-Round6
填写第三轮时，就通过第二轮选出来的f点，同样是距离变短后就更新
其余的每一轮都是通过上一轮选出来的点，距离变短就更新
| Round1 | Round2 | Round3 | Round4 | Round5 | Round6 | |
|---|---|---|---|---|---|---|
| b | 15 | 15 | 15 | 15 | 15 | 15 a-b |
| c | 2 a-c |
|||||
| d | 12 | 12 | 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 | ∞ | ∞ | 16 a-c-f-g |
16 a-c-f-g |
13 a-c-f-d-g |
|
| 集合S | c | cf | cfe | cfed | cfedg | cfedga |
至此，a点到其它点的最短路径及距离（每一行中红色的）全部求解完毕。
写在后边的话：写作不易，有帮助到你的话麻烦点赞加收藏呦。感激不尽！如有错误也请留言指正