最短路径 迪杰斯特拉算法

通过迪杰斯特拉算法计算图G中的最短路径时，需要指定起点s。

​ 此外，需要引进两个集合S和U。

• S的作用：记录已求出最短路径的顶点（以及相应的最短路径长度），
• U的作用：记录还未求出最短路径的顶点（以及该顶点到起点s的距离）。
• 初始时，S中只有起点s；
• U中是除s之外的顶点，并且U中顶点的路径是“起点s到该顶点的路径”。
• 然后，从U中找到路径最短的顶点，并将其加入到S中；
  • 接着，更新U中的顶点和顶点对应的路径。
  • 然后，再从U中找到路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。
  • 重复上述操作，直到遍历完所有顶点。