- Dijkstra是著名的图算法
- Dijkstra算法解决有权图从【一个节点到其他节点的最短路径问题】
- 以起始点为中心，向外层层扩展
Dijkstra算法的步骤
- 初始化两个集合（S，U）（S为只有顶点A的集合，U为其他顶点集合）
- 如果U不为空，对U集合顶点进行距离排序，并取出距离A最近的一个顶点D
i. 将顶点D纳入S集合
ii. 更新通过顶点D到U集合所有点的距离（如果距离更小则更新，否则不更新）
iii. 重复步骤2 - 直到U集合为空，算法完成
举例说明
-
假设要求下面这个图的最短路径，以A为起点，目前只知道A到自己的最短距离为0。
-
将A纳入集合S，集合S={A}，集合U={B，C，D，E，F}，计算集合U中各个顶点到A的距离。
-
将B纳入S（因为B到A最短），集合S={A，B}，集合U={C，D，E，F}，计算A通过B到各个顶点的距离，并更新最小值。
-
将F纳入S，再次计算A通过F到各个顶点的距离，并更新
-
将F纳入S，再次计算A通过F到各个顶点的距离，并更新
-
此时C和E到A的距离都是9，任意纳入一个顶点到S，并更新
-
最后一步
网友评论