最短路径

迪杰斯特拉算法（Dijkstra）

以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止

思路

1. 指定起点 s(即从顶点 s 开始计算)

2. 引进两个集合 S 和 U。S 的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而 U 则是记录还未求出最短路径的顶点(以及该顶点到起点 s 的距离)

3. 初始时，S 中只有起点 s；U 中是除 s 之外的顶点，并且 U 中顶点的路径是”起点 s 到该顶点的路径”。然后，从 U 中找出路径最短的顶点，并将其加入到 S 中；接着，更新 U 中的顶点和顶点对应的路径。 然后，再从 U 中找出路径最短的顶点，并将其加入到 S 中；接着，更新 U 中的顶点和顶点对应的路径。......重复该操作，直到遍历完所有顶点

参考：https://blog.csdn.net/heroacool/article/details/51014824