8. 全源最短路径¶

接下来我们考虑找到图中所有顶点对之间最短距离的问题，称为全源最短路径问题。确切地说，对于每对 \(u, v \in \mathbf{V}\)，计算 \(d(u, v)\)。除了给出任何一对之间的最短距离之外，解决此问题也是找到无向图直径的好方法，即任何一对顶点之间的最长路径。

一种解决方案是运行 Dijkstra 算法 \(|\mathbf{V}|\) 次来找到最短路径，每次计算从不同起始顶点的最短路径。如果 \(\mathbf{G}\) 是稀疏的（即 \(|\mathbf{E}| = \Theta(|\mathbf{V}|)\)），那么这是一个好的解决方案，因为基于优先队列的 Dijkstra 算法版本的总成本将是 \(\Theta(|\mathbf{V}|^2 + |\mathbf{V}||\mathbf{E}| \log |\mathbf{V}|) = \Theta(|\mathbf{V}|^2 \log |\mathbf{V}|)\)。对于稠密图，Dijkstra 算法的优先队列版本的成本为 \(\Theta(|\mathbf{V}|^3 \log |\mathbf{V}|)\)，但使用 MinVertex 的版本的成本为 \(\Theta(|\mathbf{V}|^3)\)。

另一种将处理时间限制为 \(\Theta(|\mathbf{V}|^3)\) 而与边数无关的解法称为 Floyd 算法。它是动态规划的一个实例。解决此问题的主要瓶颈在于组织搜索过程，以避免重复求解相同的子问题。这正是动态规划旨在解决的效率问题，唯一的问题是如何组织必要信息以识别某个子问题是否已被求解。我们将通过使用 \(k\) -路径来完成这种组织。定义从顶点 \(v\) 到顶点 \(u\) 的 k-路径为：其所有中间顶点（除 \(v\) 和 \(u\) 外）的索引均小于 \(k\) 的任意路径。0-路径定义为从 \(v\) 到 \(u\) 的一条直接边。下图说明了 \(k\) -路径的概念。

定义 \({\rm D}_k(v, u)\) 为从顶点 \(v\) 到顶点 \(u\) 的最短 \(k\) 路径的长度。假设我们已知从 \(v\) 到 \(u\) 的最短 \(k\) 路径。最短 \((k+1)\) 路径要么经过顶点 \(k\)，要么不经过。如果它确实经过 \(k\)，则最佳路径是从 \(v\) 到 \(k\) 的最佳 \(k\) 路径，后接从 \(k\) 到 \(u\) 的最佳 \(k\) 路径。否则，我们应该保留之前看到的最佳 \(k\) 路径。 Floyd 算法只需在三重循环中检查所有可能性。以下是 Floyd 算法的实现。算法结束时，数组 D 存储全源最短距离。

Java
Java (Generic)

/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
  for (int i=0; i<G.n(); i++) { // Initialize D with weights
    for (int j=0; j<G.n(); j++) {
      if (G.weight(i, j) != 0) { D[i][j] = G.weight(i, j); }
    }
  }
  for (int k=0; k<G.n(); k++) { // Compute all k paths
    for (int i=0; i<G.n(); i++) {
      for (int j=0; j<G.n(); j++) {
        if ((D[i][k] != Integer.MAX_VALUE) &&
            (D[k][j] != Integer.MAX_VALUE) &&
            (D[i][j] > (D[i][k] + D[k][j])))
            {
          D[i][j] = D[i][k] + D[k][j];
            }
          }
        }
      }
}

/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
  for (int i=0; i<G.n(); i++) { // Initialize D with weights
    for (int j=0; j<G.n(); j++) {
      if (G.weight(i, j) != 0) { D[i][j] = G.weight(i, j); }
    }
  }
  for (int k=0; k<G.n(); k++) { // Compute all k paths
    for (int i=0; i<G.n(); i++) {
      for (int j=0; j<G.n(); j++) {
        if ((D[i][k] != Integer.MAX_VALUE) &&
            (D[k][j] != Integer.MAX_VALUE) &&
            (D[i][j] > (D[i][k] + D[k][j])))
            {
          D[i][j] = D[i][k] + D[k][j];
            }
          }
        }
      }
}

显然，此算法需要 \(\Theta(|\mathbf{V}|^3)\) 的运行时间，它是稠密图的最佳选择，因为它（相对）快速且易于实现。

CS5040 中级数据结构与算法

Chapter 16 Graphs

8. 全源最短路径¶