aiwiki.page
中文
计算机 / 算法与理论 / floyd-warshall-algorithm

弗洛伊德–沃舍尔算法

弗洛伊德–沃舍尔算法利用动态规划,计算加权图中所有顶点对之间的最短路径距离。

16 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
图论最短路径问题算法动态规划矩阵(数学)循环不变式伪代码时间复杂度弗洛伊德–…

弗洛伊德–沃舍尔算法是一种用于求解加权图中所有顶点对之间的最短路径问题的算法。它利用动态规划计算最短路径距离矩阵,逐步允许更多顶点充当中间顶点。对于有 nn 个顶点的图,其标准实现的时间开销为 Θ(n3)\Theta(n^3),空间开销为 Θ(n2)\Theta(n^2)。该算法支持有向图和负权边,但对于需要有限最短路径距离的起终点对,从起点到终点的任何路线都不能经过负权环。

问题与表示方法

设 G=(V,E)G=(V,E) 为有向图,顶点编号为 1,…,n1,\ldots,n。每条边 (i,j)(i,j) 的权重为 w(i,j)w(i,j),表示代价、距离或其他可累加的量。任务是确定从每个顶点 ii 到每个顶点 jj 的路线的最小总权重。

算法将这些值存储在一个 n×nn\times n 的矩阵中。初始状态如下:

  • 每个对角元素为零,表示从某个顶点到自身的空路径。
  • 每条已有边的权重填入对应的矩阵元素。
  • 如果没有直接相连的边,对应元素为 +∞+\infty。
  • 如果存在平行边,只需保留其中的最小权重。
  • 负权自环必须保留,不能被零覆盖。

等价的初始化方式是:先将所有元素设为 +∞+\infty,再将对角元素设为零,随后逐条处理边,将对应元素更新为其当前值与边权重的较小者。

无向图可以通过为每条边添加两个方向来表示。然而,对于一条负权无向边,沿该边往返一次就能形成负权闭游走。因此,对于能够到达该边、并能从该边到达终点的起终点对,通常意义下的最短游走距离没有下界。

动态规划递推关系

核心思想是限制哪些顶点可以出现在路径的内部,即不包括路径的两个端点。

定义 Dij(k)D^{(k)}_{ij} 为从 ii 到 jj 的最短距离,其中只允许集合 {1,…,k}\{1,\ldots,k\} 中的顶点充当中间顶点。初始矩阵 D(0)D^{(0)} 包含直接相连的边的距离,以及对角线上的零长度路径。

当允许顶点 kk 作为中间顶点时,最短路径有两种情况:

  1. 不经过 kk,其距离仍为 Dij(k−1)D^{(k-1)}_{ij};
  2. 经过 kk,可拆分为从 ii 到 kk 的路径和从 kk 到 jj 的路径。

由此得到递推关系:

Dij(k)=min⁡(Dij(k−1),Dik(k−1)+Dkj(k−1)).D^{(k)}_{ij} = \min\left( D^{(k-1)}_{ij}, D^{(k-1)}_{ik}+D^{(k-1)}_{kj} \right).

处理完全部 nn 个顶点后,若不存在负权环,D(n)D^{(n)} 就包含了所有最短路径距离。

正确性证明使用了一个循环不变量:第 kk 轮迭代结束后,矩阵中保存的是中间顶点仅取自前 kk 个顶点的各条路径中的最优距离。不存在负权环时,总能选取一条不重复经过顶点的最短路线,因此可以在 kk 唯一出现的位置将路线拆分。

标准实现

从递推关系来看,似乎每个阶段都需要一个单独的矩阵,但标准算法只对一个矩阵进行原地更新。下面的伪代码包含可达性检查,以避免将表示无穷大的哨兵值参与加法运算:

dist = 用 INF 填充的 n × n 矩阵

for i = 1 to n:
    dist[i][i] = 0

for 每条边 (u, v, weight):
    dist[u][v] = min(dist[u][v], weight)

for k = 1 to n:
    for i = 1 to n:
        if dist[i][k] == INF:
            continue
        for j = 1 to n:
            if dist[k][j] == INF:
                continue

            candidate = dist[i][k] + dist[k][j]
            if candidate < dist[i][j]:
                dist[i][j] = candidate

不存在负权环时,枢轴对应的对角元素 dist[k][k]dist[k][k] 始终为零。因此,经由 kk 进行更新不会改变枢轴所在的行或列,使原地计算与递推关系保持一致。

在这种标准的单遍实现中,关于 kk 的循环必须位于最外层。关于 ii 和 jj 的循环可以互换。如果将 kk 移入其中任意一个循环的内部,通常会破坏动态规划的不变量,并可能产生错误结果。

示例

考虑一个有三个顶点的图,其中有向边 1→21\to2 的权重为 44,2→32\to3 的权重为 −2-2,1→31\to3 的权重为 55。初始矩阵为:

D(0)=(045+∞0−2+∞+∞0).D^{(0)}= \begin{pmatrix} 0 & 4 & 5\\ +\infty & 0 & -2\\ +\infty & +\infty & 0 \end{pmatrix}.

当允许顶点 22 作为中间顶点时,算法发现:

D13=min⁡(5,4+(−2))=2.D_{13}=\min(5,4+(-2))=2.

得到的矩阵为:

D=(042+∞0−2+∞+∞0).D= \begin{pmatrix} 0 & 4 & 2\\ +\infty & 0 & -2\\ +\infty & +\infty & 0 \end{pmatrix}.

因此,尽管存在直接相连的边,从 11 到 33 的最短路线仍然经过 22。

负权环

仅有负权边并不会使算法失效。负权环是指边权重之和为负的环,它会带来另一类问题:反复沿环行进,可以使路线的总权重任意小。

标准计算完成后,如果存在负的对角元素,即:

dist[t][t]<0,dist[t][t]<0,

就表明存在负权环。在算术运算精确的前提下,一个图存在负权环,当且仅当弗洛伊德–沃舍尔算法结束后至少有一个对角元素为负。

并非每个起终点对都会受到影响。如果存在某个顶点 tt,使得:

dist[i][t]<+∞,dist[t][t]<0,dist[t][j]<+∞.dist[i][t]<+\infty,\qquad dist[t][t]<0,\qquad dist[t][j]<+\infty.

那么,从 ii 到 jj 的距离就没有下界。

这类顶点对的距离可以标记为 −∞-\infty。这一标记过程是独立的后处理步骤;普通的松弛循环本身不会生成完整标记了负无穷距离的矩阵。

实现时必须区分三种结果:

  • 有限的最短路径距离。
  • +∞+\infty,表示终点不可达。
  • −∞-\infty,表示可达的负权环使路线代价没有下界。

路径重建

仅靠距离矩阵并不能直接得到对应的路线。可以使用一个额外的矩阵来支持路径重建,这个矩阵通常称为下一跳矩阵。

对于每条直接相连的边 i→ji\to j,初始化 next[i][j]=jnext[i][j]=j。每当发现经由 kk 能使距离严格减小时,就更新:

next[i][j]=next[i][k].next[i][j]=next[i][k].

要重建从 ii 到 jj 的路线,只需反复按照下一跳元素的指示向 jj 前进。不可达的顶点对没有下一跳,受负权环影响的顶点对则不存在有限的最短路线。

只有距离严格减小时才更新,可以避免在等长的备选路径之间进行不必要的切换。额外的矩阵需要 Θ(n2)\Theta(n^2) 空间,而重建一条有限最短路径所需的时间与该路径包含的顶点数成正比。

复杂度与实际注意事项

标准的三重嵌套循环会执行 Θ(n3)\Theta(n^3) 次距离比较。其时间复杂度不会仅仅因为输入图的边数较少而降低。无论是否另外存储实际路径,距离矩阵所需的空间均为 Θ(n2)\Theta(n^2)。

这些界限将算术运算和比较视为常数时间操作。如果权重需要使用任意精度算术,还必须考虑对这些数值表示进行运算的开销。

以下实现细节十分重要:

  • 无穷大的表示: 用作哨兵的有限值必须大于所有相关的有限距离。不能将哨兵值当作普通权重参与加法运算。
  • 溢出: 即使操作数都是有限值,也可能发生整数溢出,尤其是在负权环导致数值反复减小时。
  • 浮点运算: 舍入误差可能影响比较结果,以及对权重接近零的环的判定。
  • 内存访问: 连续遍历矩阵的行可以提高 CPU 缓存的利用率。
  • 分块: 将矩阵划分为若干块可以改善局部性,但必须按照保持依赖关系的顺序处理枢轴块,以及依赖它的同行、同列各块。
  • 并行执行: 并行计算可以加速经过适当同步的各个阶段内的更新。不顾枢轴依赖关系而任意分配所有迭代,并不等价于该算法。

相关算法与扩展

沃舍尔传递闭包算法

将数值距离替换为布尔可达性,就得到了与之密切相关的传递闭包算法:

Rij←Rij∨(Rik∧Rkj).R_{ij} \leftarrow R_{ij}\lor(R_{ik}\land R_{kj}).

这里,RijR_{ij} 记录从 ii 是否能到达 jj。将对角元素初始化为真,会把零长度路径计入其中,得到自反传递闭包;若将其初始化为假,则记录的是通过正长度路径的可达性,在存在环时,相应的对角元素会变为真。

数值最短路径版本使用取最小值和加法,对应于布尔版本中的逻辑或与逻辑与。

与其他最短路径方法的比较

迪ijkstra算法用于求解边权非负的单源问题。在稀疏图上,从每个顶点分别运行一次该算法通常是更好的选择。

贝尔曼–福特算法允许负权边,并能检测从单个源点可达的负权环,但对所有源点重复运行该算法,其开销通常高于弗洛伊德–沃舍尔算法。

约翰逊算法将贝尔曼–福特重赋权与多次迪ijkstra搜索相结合。它支持不存在负权环的含负权边图,通常更适合稀疏图上的所有顶点对最短路径问题。

弗洛伊德–沃舍尔算法对于稠密图、中等规模的输入,以及需要完整距离矩阵的应用仍然很有用。例如,距离表预处理、加权网络分析,以及差分约束系统的检验。

历史发展

该算法的历史涉及几种密切相关的形式。贝尔纳·鲁瓦于 1959 年发表了一种相关的寻路方法。1962 年,斯蒂芬·沃舍尔发表了用于计算传递闭包的布尔矩阵算法,同年罗伯特·W. 弗洛伊德发表了数值最短路径版本。

弗洛伊德–沃舍尔这一复合名称体现了两者共用的中间顶点递推关系。包含鲁瓦姓名的名称则是对其早期贡献的认可,不过不同教材和软件库的命名惯例有所不同。