最短路径(Dijkstra算法)

最短路径问题是图论中的经典问题之一，它要求找到两个顶点之间的最短路径。

Dijkstra算法是解决最短路径问题的一种算法，它的基本思想是从起点开始，逐步扩展到其他顶点，不断更新每个顶点到起点的最短距离。

具体的步骤如下：

创建一个列表distances，用于存储每个顶点到起点的最短距离，初始值为无穷大。

将起点的最短距离设置为0，表示起点到自身的距离为0。

创建一个优先队列，用于存储待遍历的顶点及其到起点的距离。

将起点及其到起点的距离加入优先队列。

循环执行以下步骤，直到优先队列为空：

a. 从优先队列中取出一个顶点v及其到起点的距离d。

b. 如果d大于distances[v]，则说明已经找到了更短的路径，跳过该顶点。

c. 否则，更新顶点v的最短距离distances[v]为d。

d. 遍历顶点v的所有邻接顶点，计算从起点经过顶点v到达邻接顶点的距离，并将其加入优先队列。

最终distances列表中存储的就是每个顶点到起点的最短距离。

Dijkstra算法的时间复杂度为O((V+E)logV)，其中V为顶点数，E为边数。它适用于没有负权边的图。

需要注意的是，Dijkstra算法只能计算单源最短路径，即从起点到其他顶点的最短路径。要计算所有顶点之间的最短路径，可以对每个顶点都执行一次Dijkstra算法。