Python中的Dijkstra算法

给定图和源顶点，找出源顶点与图中每个顶点之间的最短路径。

Dijkstra 方法和 Prim 的最小生成树方法非常相似。与 Prim 的 MST 类似，我们以指定的源为根创建一棵 SPT（最短路径树）。我们维护两个集合；一个集合包含已包含在最短路径树中的顶点，而另一个集合包含尚未包含在树中的顶点。在算法的每个阶段，我们都在另一个集合（仍需要包含的集合）中寻找一个与源的距离最短的顶点。

Dijkstra 方法确定单源顶点与给定图中每个其他顶点之间最短路径所采取的精确步骤如下。

算法

1. 创建一个名为 sptSet（最短路径树集）的集合，用于跟踪已包含在最短路径树中的顶点，这些顶点的最短距离已从源确定。此集合最初为空。
2. 为输入网络中的每个顶点分配一个距离值。开始时，将所有距离值设置为 INFINITE。将源顶点的距离值设置为 0，以确保它首先被选中。
3. 即使 sptSet 缺少某些顶点
   • 选择一个在 sptSet 中未出现的、距离值最小的顶点 u。
   • 将 u 添加到 sptSet 中。
   • 更新其每个邻居顶点的距离。遍历所有邻居顶点以更新距离值。如果边 u-v 的权重加上 u（来自源）的距离值对于每个邻居顶点 v 小于 v 的距离值，则应更新 v 的距离值。

程序代码

输出

Vertex      Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

• 时间复杂度： Dijkstra 算法的时间复杂度为 O(V2)。这是因为该算法使用两个嵌套循环来迭代地搜索网络，以找到连接所有节点到源节点的最短路径。
• 空间复杂度： Dijkstra 算法的空间复杂度为 O(V)，其中 V 是图中顶点的数量。这是因为该方法可以在大小为 V 的数组中记录源节点与每个其他节点之间的距离。