最短路径(Dijkstra算法)

最短路径问题是图论中的经典问题之一，它要求找到两个顶点之间的最短路径。
Dijkstra算法是解决最短路径问题的一种算法，它的基本思想是从出发点开始，逐渐扩大到其他顶点，不断更新每一个顶点到出发点的最短距离。
具体的步骤以下：
1. 创建一个列表distances，用于存储每一个顶点到出发点的最短距离，初始值为无穷大。
2. 将出发点的最短距离设置为0，表示出发点到本身的距离为0。
3. 创建一个优先队列，用于存储待遍历的顶点及其到出发点的距离。
4. 将出发点及其到出发点的距离加入优先队列。
5. 循环履行以下步骤，直到优先队列为空：
a. 从优先队列中取出一个顶点v及其到出发点的距离d。
b. 如果d大于distances[v]，则说明已找到了更短的路径，跳过该顶点。
c. 否则，更新顶点v的最短距离distances[v]为d。
d. 遍历顶点v的所有邻接顶点，计算从出发点经过顶点v到达邻接顶点的距离，并将其加入优先队列。
6. 终究distances列表中存储的就是每一个顶点到出发点的最短距离。
Dijkstra算法的时间复杂度为O((V+E)logV)，其中V为顶点数，E为边数。它适用于没有负权边的图。
需要注意的是，Dijkstra算法只能计算单源最短路径，即从出发点到其他顶点的最短路径。要计算所有顶点之间的最短路径，可以对每一个顶点都履行一次Dijkstra算法。