最短路径算法(一):Dijkstra算法

一、算法介绍

迪杰斯特拉(Dijkstra)算法用于计算一个节点到其他所有节点的最短路径。 

1、单源

2、贪心算法

3、适用无负权边的情况

二、算法思想

准备2个集合 S 和 U

S保存已经计算好的源节点到此节点最短距离

U保存未计算好最短记录的点

每次从U中取出最小的值，放入S中，其他节点根据此节点重写计算最短距离

图解

以D为源点

第一步：

S={D(0)}

U={A(无穷大),B(无穷大),C(3),E(4),F(无穷大),G(无穷大)}

第2步：

S={D(0),C(3)}

U={A(无穷大),B(13),E(4),F(9),G(无穷大)}

 第3步：

S={D(0),C(3),E(4)}

U={A(无穷大),B(13),F(6),G(12)}

第4步：

S={D(0),C(3),E(4),F(6)}

U={A(22),B(13),G(12)}

 第5步：

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

U={A(22),B(13)}

第6步：

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

U={A(22)}

第7步：

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

U={}

 U中无点时，S即为所求的单源节点到其他所有节点的最短距离

时间复杂度O(V^2)

参考：

https://blog.csdn.net/qq_37796444/article/details/80663810