介绍

最短路径，两结点之间最短的路径（可以是非邻接结点）

算法：

迪杰斯特拉（Dijkstra）算法

贪心算法

需要指定起点（源点）

引进两个集合S和U：

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。

然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。

然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。
…
重复该操作，直到遍历完所有顶点。

S是已计算出最短路径的顶点集合
U是未计算除最短路径的顶点的集合

将顶点D加入到S中：

S={D(0)}
U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}

注: C(3)表示C到起点D的距离是3。

将顶点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(∞)}

将顶点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)}

将顶点F加入到S中。
此时，

S={D(0),C(3),E(4),F(6)}
U={A(22),B(13),G(12)}

将顶点G加入到S中
此时，

S={D(0),C(3),E(4),F(6),G(12)}
U={A(22),B(13)}

将顶点B加入到S中。
此时，

S={D(0),C(3),E(4),F(6),G(12),B(13)}
U={A(22)}

将顶点A加入到S中。
此时，

S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}

此时，起点D到各个顶点的最短距离就计算出来了：