理解Floyd-Warshall算法

我们之前分别讨论了Dijkstra算法和Bellman-Ford算法，它们解决的都是单源最短路径问题。本文讨论的Floyd-Warshall算法（下称FW算法）则适用于解决可有负权边但不可有负权环的“全局最短路径问题”（all-pairs shortest path problem，或叫做“任意两点间的最短路径问题”)。

为了方便阐述思路，下文的讨论里默认处理的问题还满足下面的特点：

1. 有权图
2. 两节点之间最多有一条边
3. 无自回路（任何节点无指向自身的边）

下图为一个示例：

image

不满足上面三条限制的图需要先进行转化，然后才能用下述的FW算法来解决。其可行性和具体过程，留给读者自行探索。

算法思路

若图G有n个节点（即n = |V|），将这所有节点做任意一个排序，依次记为v_1, v_2, ..., v_n。对于任意的起点u和任意的终点w，从它们之间的路径中挑出所有中间点只含前k个节点（即{v_1, v_2, ..., v_k}，其中k < n）的那些，组成一个集合记为P(u, w, k)，并且假设我们已经知晓其中最短路径的长度，记为d(u, w, k)；那么从u到w的、所有中间点只含前k+1个节点的路径组成的集合可以记为P(u, w, k+1)，它们中间最短者的长度可以记为d(u, w, k+1)。可以很容易想明白这么一个关系，P(u, w, k+1)是P(u, w, k)的一个超集，而且属于前者而不属于后者的路径一定经过第k+1个节点，也就是v_(k+1)。如果P(u, w, k+1)中的某条最短路径不经过v_(k+1)，那么d(u, w, k+1)就等于d(u, w, k)。如果经过，那么首先可以知道，这条最短路径一定只经过v_(k+1)一次，否则路径中有回路，与最短矛盾；这也意味着，这条路径可以分为两半——从u到v_(k+1)的路径和从v_(k+1)到w的路径，且有：

1. 它们的中间点都只由前k个节点组成
2. 前一半在所有从u到v_(k+1)的中间点只含前k个节点的路径中一定是最短的，其长度为d(u, v_(k+1), k)
3. 后一半在所有从v_(k+1)到w的中间点只含前k个节点的路径中一定最短，其长度为d(v_(k+1), w, k)

那么此时这条最短路径的长度为d(u, v_(k+1), k) + d(v_(k+1), w, k)。如下图所示：

image

综上，可以得到下面这条重要结论：

d(u, w, k+1) = min(d(u, w, k), d(u, v_(k+1), k) + d(v_(k+1), w, k))

要证明上面思路的正确性，我们还得考虑一下基础情况。当k = 0时，对于图中任意的起终点u和w，如果存在从u到w的边，那么记d(u, w, 0) = G[u][w]，否则记d(u, w, 0) = ∞。如此一来，算法的循环不变性质可以表述为：

• 初始为真：在循环之前（k = 0）时，对于任意的u和w，d(u, w, k)确实为从u直接到w的最短路径的长度（不存在时为无穷大）
• 迭代不变：这在前面已经证明
• 终止得证：那么在算法终止时，也就是第n次迭代结束后，d(u, w, n)的值为从u到w（中间点可以为所有节点）的最短路径的长度

代码实现

根据上面的思路，我们可以给出如下的代码实现。下面的代码出自Python Algorithms一书，稍有改动，下同。

from copy import deepcopy
from math import inf


def floyd_warshall(G):
    D = deepcopy(G)
    for v in G:
        for u in G:
            for w in G:
                current = D[u].get(w, inf)
                shortcut = D[u].get(v, inf) + D[v].get(w, inf)
                D[u][w] = min(current, shortcut)
    return D

在上面的代码里，图G由G表示：对于G中任意节点v，G[v]本身也是一个dict，如果存在边(v, w)，则G[v][w]是该边的权重。因为这里限制了自回路的情况，对任意的节点v，有G[v].get(v, inf)等于inf而非0；这一点请留意。

首先讲讲算法的空间复杂度。在上节的思路分析里，我们用了起点、终点、可用中间点的最大序号三个参数来表示子问题的解，所以很容易以为代码中需要一张三维的表来做记录，而实际上这里相当于只用了一张二维的表，D，它的结构与G完全相同。其实说到这里，应该已经可以明确，Floyd-Warshall算法运用的是动态规划思想。动态规划的关键在于把原问题拆分为互有重叠的子问题。FW算法就是按照可用中间点的最大序号，把原问题分拆成了很多级子问题。而D就是用来存储子问题的解的。之所以不需要三维而只需二维的表，是这个大问题的内在结构决定的：每一级的子问题只依赖于低一级的子问题的解，而不需要更低级别的子问题的解，所以可以覆盖原来的值，故而总体上的空间复杂度为O(|V|²)。

算法的时间复杂度显然为O(|V|³)，因为有三层循环。要注意的是循环的顺序：最外层的循环变量一定得是中间点。这是因为子问题是以可用中间点的最大序号来分级的，在解决某一级子问题的时候，需要所有低一级的子问题都已经有解了。

强调一点

从上面的分析来看，FW算法的思想说穿了不难理解，相应地，其代码实现也可以很简单。但其精妙或者说最难想到之处，就是它构建子问题的方法：在缩小了问题规模的同时保证了子问题与原问题有同样的结构。做到这一点，依靠的是引入一个不怎么直观的限制：路径中间点所能选择的集合。

其实这种引入新的限制参数来分拆问题的技巧，尤其在动态规划的算法里，不算少见。例如硬币面额组合问题的解法，就用到了这个技巧。以后在遇到新问题时，如果觉得可以用动态规划来解，但是不知道如何分拆为子问题时，不妨打开下思路，试试看能不能引入新的限制，也许就能豁然开朗。

结语

本文讨论了Floyd-Warshall算法，这里对关键点做个总结：

• FW算法解决的是全局最短距离问题，适用的图中允许有负权边，但不可有负权环
• FW算法运用了动态规划的思想，其核心在于限制路径中间点的选择
• FW算法的时间负责度为O(|V|³)，空间复杂度可以达到O(|V|²)