Floyd-Warshall 多源最短路径算法

发表于 2024-02-07 更新于 2024-11-19 分类于 Algorithm Waline：

单源最短路径算法和多源最短路径算法的区别在于它们解决的问题不同。

单源最短路径算法是指在给定一个起点，计算该起点到图中其他所有顶点的最短路径。其中最著名的算法是Dijkstra算法和Bellman-Ford算法。Dijkstra算法适用于有向图中没有负权边的情况，而Bellman-Ford算法可以处理有负权边的情况。

多源最短路径算法是指计算图中任意两个顶点之间的最短路径。其中最著名的算法是Floyd-Warshall算法。Floyd-Warshall算法通过动态规划的方式计算任意两个顶点之间的最短路径，可以处理有向图和负权边的情况。

总结起来，单源最短路径算法解决的是从一个起点到其他所有顶点的最短路径问题，而多源最短路径算法解决的是任意两个顶点之间的最短路径问题。

我们之前的博客介绍过Dijkstra算法，这次主要是记录下Floyd算法。

算法解析

Floyd-Warshall 算法使用一种不同的动态规划公式来解决所有结点对最短路径问题，运行时间为 $O(n^3)$ ，图上可以存在负权重的边，但是不存在负权重的环。

Floyd 算法考虑的是一条最短路径上的中间结点。

中间节点：简单路径 $p = <v_1, v_2, ..., v_l>$ 上的中间节点指的是路径p上除了 $v_1$ 和 $v_l$ 之外的任意节点，也就是集合 $\{v_2,v_3,...v_{l-1}\}$ 中的结点。

假定图G中所有节点为V={1,2,3,4…,n}，考虑其中一个子集 $\{1，2，3，...，k\}$ ，对于任意节点对 $i,j \in V$ ，考虑从i到j的所有中间节点均取自于集合 $\{1,2,3,...k\}$ 的那些路径，并设p为其中权重最小的路径。我们分别考虑k是否是路径p上一个中间节点的情况

注意：这里k的含义是路径中所有节点中的序号中最大的

如果k不是p上的中间节点，则p上所有中间节点都属于集合{1,2,3,…k-1}。因此，从i到j且中间节点均取自于{1,2,3…,k-1}的一条最短路径同时也是从i到j且中间节点均取自于{1,2,3,…,k}的一条最短路径
如果节点k是路径p上的中间节点，则将路径p分解成 $p_1 : i \rightarrow k$ 和 $p_2: k \rightarrow j$ 。可得 $p_1$ 是从结点 i到结点 k 的，中间结点全部取自集合 {1，2，3，… k - 1}的一条最短路径（因为 k 是末尾结点）。类似的， $p_2$ 是从结点 k到结点 j的，中间结点全部取自集合 {1，2，3，… k - 1}的一条最短路径。

我们假设 $d_{ij}^{k}$ 是从节点i到节点j的所有中间节点全部取自 $\{1,2,3,...,k\}$ 的最短路径权重。k=0时，意味着路径只有一条边构成，也就是i直接到j的距离。

根据以上定义，我们可以递归定义：

d_{ij}^k = \begin{cases} w_{ij} & k=0 \\ min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1}) \end{cases}

我们可以自底向上计算最短路径的权重，算法输入为n*n的矩阵W，输出最短路径权重矩阵 $D^n$ ，伪代码如下：

算法源码

用js简单实现一个floyd算法：

function floydWarshall(graph) {
  const n = graph.length;
  const dist = Array(n)
    .fill()
    .map(() => Array(n).fill(Infinity));

  // 初始化距离矩阵
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else if (graph[i][j] !== 0) {
        dist[i][j] = graph[i][j];
      }
    }
  }

  // 计算最短路径
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

// 示例图
const graph = [
  [0, 5, Infinity, 10],
  [Infinity, 0, 3, Infinity],
  [Infinity, Infinity, 0, 1],
  [Infinity, Infinity, Infinity, 0]
];

const shortestPaths = floydWarshall(graph);
console.log(shortestPaths);

从这个算法的具体实现中，我们可以看出，最重要的部分就是计算最短路径的三层嵌套循环，而且我们需要注意，我们的递推矩阵是二维的。

我们可以这样理解这个三层的嵌套循环，最外层的k表示当前可以用到的序号最大的点的序号，在此基础上内层的双层循环更新整个最短路径矩阵，然后利用k=n时的最短路径矩阵去递推k=n+1时的最短路径矩阵。

如果增加一条边，如何更新最短路径矩阵

现在我们已经构建好了最短路径矩阵，如果这个时候我们要增加一条边，我们如果更新整个最短路径矩阵呢？是否需要重新走一遍刚才的流程？

答案是否定的。

假设我们增加一条从x到y权重为w的边，我们可以通过以下方式来更新最短路径矩阵D：

w是否小于 $D[x][y]$ ，如果 $w \ge D[x][y]$ ，那么整个矩阵都不需要更新
如果 $w \lt D[x][y]$ ，那么只需要遍历最短路径矩阵D中的每一项，比较 $D[i][j]$ 与 $D[i][x] + w + D[y][j]$ 的大小，选择其中小的一项作为矩阵中的新值

代码如下：

class Graph {
    constructor(n, edges) {
        this.INF = Math.floor(Number.MAX_SAFE_INTEGER / 3); // 防止更新最短路时加法溢出
        this.d = new Array(n).fill(null).map(() => new Array(n).fill(this.INF)); // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
        for (let i = 0; i < n; ++i) {
            this.d[i][i] = 0;
        }
        for (const e of edges) {
            this.d[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边和自环）
        }
        for (let k = 0; k < n; ++k) {
            for (let i = 0; i < n; ++i) {
                for (let j = 0; j < n; ++j) {
                    this.d[i][j] = Math.min(this.d[i][j], this.d[i][k] + this.d[k][j]);
                }
            }
        }
    }

    addEdge(e) {
        const x = e[0], y = e[1], w = e[2], n = this.d.length;
        if (w >= this.d[x][y]) { // 无需更新
            return;
        }
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                this.d[i][j] = Math.min(this.d[i][j], this.d[i][x] + w + this.d[y][j]);
            }
        }
    }

    shortestPath(start, end) {
        const ans = this.d[start][end];
        return ans < this.INF / 3 ? ans : -1;
    }
}