Dijkstra 算法

• 将图中的顶点分为两个集合：

  • 集合 A 保存已经计算出最短路径的顶点集，初始时，A 中只包含源点
  • 集合 B 保存尚未计算出最短路径的顶点集，初始时，B 包含除源点外的其它所有顶点

• 辅助数组 D[] 的每个分量表示一个顶点的最短路径。初始时，源点的最短路径是 0

• 重复执行下面的操作，直到 B 空：

  • 如果 n ∈ B，则 D_estimate[n] = Min_{m ∈ A}(D[m] + Weight(m, n))

    • 即 D_estimate[n] 等于所有 A 中邻接到 n 的顶点的最短路径加上相关联的弧的权值中的最小值
    • 如果无法从 A 中的顶点达到 n，那么 D_estimate[n] = ∞

  • 设 B 中 D_estimate 值最小的顶点是 m，则：

    • 将 m 从 B 中删除
    • 将 m 加入到 A 中
    • D[m] = D_estimate[m]

证明

下面使用循环不变式证明 Dijkstra 算法。

• 不变式：
  对 A 中任意顶点 m，D[m] 是其最短路径
• 初始：
  初始时，A 中只有源点，且源点的最短路径是 0，所以不变式成立
• 保持：
  设 n 是 B 中 D_estimate 值最小的顶点。
  假设 D_estimate[n] 不是 n 的最短路径，D[n] 是 n 的最短路径，则 D[n] < D_estimate[n]。
  因为 D_estimate[n] 是只通过 A 中的顶点的最短路径，并且它不是 n 的最短路径，那么 n 的最短路径一定会经过非 A 中的顶点。假设路径上第一个非 A 中的顶点是 j，则 n 的最短路径是 s -> ... -> j -> ... -> n，所以 D_estimate[j] <= D[n] < D_estimate[n]。这与 n 是 B 中 D_estimate 值最小的顶点相矛盾，所以 D_estimate[n] 是 n 的最短路径
• 结束：
  当循环结束时，A 中的任意顶点 m 的最短路径是 D[m]

Python 实现

tim-chow 的 Github