迪杰斯特拉（Dijkstra）算法

• Dijkstra是著名的图算法
• Dijkstra算法解决有权图从【一个节点到其他节点的最短路径问题】
• 以起始点为中心，向外层层扩展

Dijkstra算法的步骤

• 初始化两个集合（S，U）（S为只有顶点A的集合，U为其他顶点集合）
• 如果U不为空，对U集合顶点进行距离排序，并取出距离A最近的一个顶点D
  i. 将顶点D纳入S集合
  ii. 更新通过顶点D到U集合所有点的距离（如果距离更小则更新，否则不更新）
  iii. 重复步骤2
• 直到U集合为空，算法完成

举例说明

1. 假设要求下面这个图的最短路径，以A为起点，目前只知道A到自己的最短距离为0。

   
   

2. 将A纳入集合S，集合S={A}，集合U={B，C，D，E，F}，计算集合U中各个顶点到A的距离。

   
   

3. 将B纳入S（因为B到A最短），集合S={A，B}，集合U={C，D，E，F}，计算A通过B到各个顶点的距离，并更新最小值。

   
   

4. 将F纳入S，再次计算A通过F到各个顶点的距离，并更新

   
   

5. 将F纳入S，再次计算A通过F到各个顶点的距离，并更新

   
   

6. 此时C和E到A的距离都是9，任意纳入一个顶点到S，并更新

   
   

7. 最后一步