最短路径
迪杰斯特拉算法(Dijkstra)
以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止
思路
指定起点 s(即从顶点 s 开始计算)
引进两个集合 S 和 U。S 的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而 U 则是记录还未求出最短路径的顶点(以及该顶点到起点 s 的距离)
初始时,S 中只有起点 s;U 中是除 s 之外的顶点,并且 U 中顶点的路径是”起点 s 到该顶点的路径”。然后,从 U 中找出路径最短的顶点,并将其加入到 S 中;接着,更新 U 中的顶点和顶点对应的路径。 然后,再从 U 中找出路径最短的顶点,并将其加入到 S 中;接着,更新 U 中的顶点和顶点对应的路径。......重复该操作,直到遍历完所有顶点