Dijkstra算法图解

img

以上图G4为例,来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。

img

初始状态 :S是已计算出最短路径的顶点集合,U是未计算除最短路径的顶点的集合!
第1步 :将顶点D加入到S中。
此时,S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起点D的距离是3。

第2步 :将顶点C加入到S中。
上一步操作之后,U中顶点C到起点D的距离最短;因此,将C加入到S中,同时更新U中顶点的距离。以顶点F为例,之前F到D的距离为∞;但是将C加入到S之后,F到D的距离为9=(F,C)+(C,D)。
此时,S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。

第3步 :将顶点E加入到S中。
上一步操作之后,U中顶点E到起点D的距离最短;因此,将E加入到S中,同时更新U中顶点的距离。还是以顶点F为例,之前F到D的距离为9;但是将E加入到S之后,F到D的距离为6=(F,E)+(E,D)。
此时,S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。

第4步 :将顶点F加入到S中。
此时,S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步 :将顶点G加入到S中。
此时,S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步 :将顶点B加入到S中。
此时,S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步 :将顶点A加入到S中。
此时,S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此时,起点D到各个顶点的最短距离就计算出来了: A(22) B(13) C(3) D(0) E(4) F(6) G(12)

摘自:https://wangkuiwu.github.io/2013/04/14/dijkstra-cplus/