【B3647】Floyd 算法

一扶苏一 · 2022-11-23 19:40:56 · 题解

【B3647】Floyd 算法

Preface

这是我在大学“数据结构”课程的“翻转课堂”活动的授课任务，即向同学讲解 Floyd 算法。因为课堂的听众不全有竞赛经历，所以我事实上在讲课的前半部分通过几道例题简单介绍了动态规划算法作为引入，在本文中略去。如果你还不了解动态规划和“阶段”“状态”等相关理论，可以先通过课件了解动态规划。完整课件可以点击这里下载。

对本文和课件的转载必须注明作者和出处。

Floyd-Warshal Algorithm 是一个基于动态规划的全源最短路算法。它可以高效地求出图上任意两点之间的最短路。

Preliminaries

如无特殊约定，本文用 n 表示图的顶点数，m 表示边数。一张带权有向图被定义为 (V,E,w)，其中 V 是点集，E 是边集，w: E \rightarrow \mathbb{R} 是边集向实数集的映射，称为边权。根据需要，这一映射可能是向非负实数集的。我们的研究着眼于带权有向图上的全源最短路。在无向图上，只需要把边拆成两条有向边即可。

我们用如下的邻接矩阵结构存图：

约定忽略图的自环，重边仅保留权值最小的一条。

A Rough Work

我们首先考虑边权均非负的情况。

采用动态规划的方法解决这一问题：设 f_{k, u, v} 表示当只考虑编号不大于 k 的顶点和 u,v 自身时，u 到 v 的最短路，即要求 u 到 v 的路径上的顶点（不包括 u,v 自身）编号不大于 k，考察此时的最短路。

初始状态显然有 f_{0, u, v} = G_{u, v}。

考虑计算 f_{k,u,v}，只考虑 u, v 自身和编号不大于 k 的顶点，此时的最短路有两种方案：

1. 不经过编号为 k 的顶点。则此时的最短路就是 f_{k - 1, u, v}；
2. 经过编号为 k 的顶点。那么我们此时的最短路会通过 k 号顶点。我们把 u 到 v 的路径拆成 u\rightarrow k 和 k \rightarrow v 两条。注意到此时 u 到 k 的路径上的顶点显然应该都小于 k（因为没有负边，走一个点超过两次不会得到任何正收益），k 到 v 的路径同理。于是这两条路径的最短路分别是 f_{k-1, u, k} 和 f_{k-1, k, v}，如图：
   

综合两种情况，转移就是 f_{k,u,v} = \min(f_{k-1,u,v}, f_{k-1,u,k}+f_{k-1,k,v})

容易写出代码：

for k := 1 to n:
  for u := 1 to n:
    for v := 1 to n:
      f(k,u,v) := min{f(k-1,u,v), f(k-1,u,k)+f(k-1,k,v)}

在这里，k 是我们转移中的阶段。

Space Cost Optimization

A Classic Skill

易见在上一部分里我们提出的算法时空复杂度均为 \Theta(n^3)。时间复杂度难以优化，但是注意到我们最后只要 \Theta(n^2) 个信息。于是考虑对空间复杂度进行优化。

考察转移：f_{k,u,v} = \min(f_{k-1,u,v}, f_{k-1,u,k}+f_{k-1,k,v}) 注意到 f_k 的值只与 f_{k-1} 有关，和再之前的状态无关，且我们最终关心 f_n，所以 k-2 及以前的状态可以无需记录。

采用经典的“滚动数组”的技巧，令 g_{1, u, v} 表示当前状态的对应 dp 值，g_{0, u, v} 表示上一阶段的 dp 值。（这就是说，设当前在计算 f_k，则令 g_{1, u, v} = f_{k, u, v}，g_{0, u, v} = f_{k - 1, u, v}）。

则转移可以写成：g_{1, u, v} = \min(g_{0, u, v}, g_{0, u, k} + g_{0, k, v})。

注意每个阶段的转移结束之后（即 f_k 的所有状态被计算完毕后），g_1 成了下一个阶段的“上一个阶段”，此时需要用 g_1 替换 g_0，计算新的 g_1，写作代码就是

for k := 1 to n:
  for u := 1 to n:
    for v := 1 to n:
      g(1,u,v) := min{g(0,u,v), g(0,u,k)+g(0,k,v)}
  for u := 1 to n:
    for v := 1 to n:
      g(0,u,v) := g(1,u,v)

这样，我们只需要一个大小为 2n^2 的数组就完成了计算。空间复杂度被降为了 \Theta(n^2)。

Further Optimization

考察原始的转移方程：f_{k,u,v} = \min(f_{k-1,u,v}, f_{k-1,u,k}+f_{k-1,k,v})。

不难发现：f_{k,u,k} = f_{k - 1, u, k}，f_{k, k, v} = f_{k - 1, k, v}。这是因为非负权图最短路显然不会经过同一个点两次。

于是滚动数组后的转移可以写成：g_{1, u, v} = \min(g_{0, u, v}, g_{0/1, u, k} + g_{0/1, k, v})。

这就是说，在转移 g_1 时，u 到 k 和 k 到 v 的最短路是否被更新是无关紧要的。

我们直接令 g_{u, v} 表示当前或上一阶段的对应 dp 值，则转移可以直接写成：g_{u, v} = \min(g_{u, v},g_{u, k} + g_{k, v})，初始状态为 g_{u, v} = G_{u, v}。

写作代码就是：

for k := 1 to n:
  for u := 1 to n:
    for v := 1 to n:
      g(u,v) := min{g(u,v), g(u,k)+g(k,v)}

这就是我们所熟悉的 Floyd 算法的最常见形式。其时间复杂度为 \Theta(n^3)，空间复杂度为 \Theta(n^2)，相比于上一个算法，我们虽然没能在空间复杂度上做出改进，但是优化掉了严格 n^2 的空间占用。

Application on Graphs with Negative Weight

Graphs Without Negative Circles

我们已经得到了非负权图上的 Floyd 算法。是时候尝试把它拓展到负权图上了。

我们首先考虑图上没有负圈的情况。此时任意两点之间都有唯一的最短路。

考察在非负权图上的转移：

为了计算 f_{k,u,v}，此时的最短路有两种方案：

1. 不经过编号为 k 的顶点。则此时的最短路就是 f_{k - 1, u, v}；
2. 经过编号为 k 的顶点。那么我们此时的最短路会通过 k 号顶点。我们把 u 到 v 的路径拆成 u\rightarrow k 和 k \rightarrow v 两条。注意到此时 u 到 k 的路径上的顶点显然应该都小于 k，k 到 v 的路径同理。此时的最短路是 f_{k - 1, u, k} + f_{k - 1, k, v}。

考察第二条转移成立的条件是「u 到 k 和 k 到 v 的路径上经过的顶点都应该是小于 k 的」。这一条在无负圈的负权图上是否成立？

结论是成立。因为如果经过了 k 两次且最短路的长度减小了，说明图上有一个从 k 起到 k 止的负圈。这与我们没有负圈的假设矛盾。

所以非负权图上的 Floyd 算法可以直接推广到无负圈的负权图上。

Graphs with Negative Circles

考察有负圈的情况，Floyd 算法能否确定某张图是否存在负圈？又能否确定那些不受负圈影响的顶点对之间的最短路？

先跑一遍 Floyd 算法，把结果记下来。以结果为初始边权再跑一遍 Floyd 算法（也就是在第一次 Floyd 跑完的数组上直接再跑一轮）。对比两次算法的结果。如果两个顶点对 (u,v) 间的最短路产生了变化，说明该最短路经过了负圈，不存在真正意义上的“最短路”。没有产生变化的点对是不受负圈影响的点对，此时计算出的是正确的最短路。