图论 - Floyd 算法

Floyd-Warshall 算法是图论中的一个经典多源最短路径算法，今天我和大家一起来学习这个算法。

我不想像其他能查到的大部分介绍该算法的中文文章一样，直接贴算法代码；相反，我想和大家一起讨论这个算法的思想，并且证明它的正确性。

什么是多源最短路径？

对于已经知道这个算法解决了什么问题的朋友，这部分可以跳过。

首先我们要知道 Floyd-Warshall 算法解决了什么样的问题：什么是多源最短路径？

最短路径

对某个图 $G \langle {V, E} \rangle$定义一个序列结构 $P_l$，从顶点 $v_1$ 开始，到节点 $v_l$ 结束：
$$
(v_1, e_1, v_2, e_2, …, e_{l-1}, v_l)
$$
其中 $v_i \in V$ 式图中的顶点，而 $e_i \in E$ 是图中的边，并且符合条件：

• $e_i$ 的两个节点必须为 $v_i, v_{i + 1}$，也就是序列中前后的两个节点
• $\forall i, j < l, e_i, e_j \in P_l, e_i \neq e_j$，也就是说序列中的任意两条边不同

这样的序列结构我们称为路径；对于无权图，路径中的边数量称为路径的长度，相应的在赋权图中，长度定义为路径中边的权值之和。

显然，对于图中的两个顶点，可能存在不止一条路径将其连接起来，最短路径就是在两个顶点形成的路径集合中长度最短的那条路径。

单源与多源

在图论算法中有两类最短路径算法（Shortest Path Algorithm）：

• 单源最短路径问题

  这类问题需要求解的是图从某一个给定的顶点 $v$ 到图中剩下所有点的最短路径

• 多源最短路径问题

  这类问题需要求解的是图中任意两顶点的最短路径问题

一般来说，在计算最短路径之前，我们都需要判断两顶点的可达性问题，也就是两顶点间是否存在路径，我们可以用BFS/DFS算法去做，之后有机会我们介绍一下这两个算法，这里我们假设两个顶点间存在可达性。

如何解决

在明确了我们要解决什么问题之后，我们思考问题如何解决。

我们构造一个距离变量 $d_{k, u, v}$ 用于描述顶点 $u, v$ 之间的最短路径长度，其中：

• $k$ 表示该最短路径中经过了 $k$ 个其他节点
• $u, v$ 表示起、终点

对于顶点 $u, v$ 来说，其之间的最短路径无外乎就两种情况：

• 最短路径为 $(u, e_{uv}, v)$

  这种情况下，两个顶点是相邻的，并且最短路径就是他们之间的邻边，最短路径中不经过任何其他顶点

• 最短路径为 $(u, e_1, e_2, …, e_k, v)$

  这种情况下，两个顶点的最短路径中间经过了 $k$ 个顶点 $(k \geq 1)$

那么，如果我们要查找两个节点之间的最短路径，就可以这样办：

0. 在顶点集合 $V - {u, v}$ 中拿出一个顶点 $w$
1. 如果 $u \rightarrow w \rightarrow v$ 的距离小于 $u \rightarrow v$ 的距离，那么把当前已知 $u \rightarrow v$ 的距离更新为它
2. 如果 $u \rightarrow w \rightarrow v$ 的距离大于 $u \rightarrow v$ 的距离，那么保持 $u \rightarrow v$ 的距离

这样，当顶点集合 $V - {u, v}$ 中的所有节点都被检查过后，就能找到 $u \rightarrow v$ 的最短路径。

如果用公式表示的话，我们可以得到一个经过节点 $k$ 的最短路径状态转移方程：
$$
d_{k, i, j} = \min { f_{k - 1, i, j}, f_{k - 1, i, k} + f_{k - 1, k, j} }
$$

如何实现

既然我们要寻找每一对顶点之间的最短距离，那么我们就使用邻接矩阵保存图中的权值关系，节点自身到自身的距离设置为 $0$，到没有邻接关系节点的距离设置为 $\infty$ 之后：

• 对 每一个节点，遍历 图中的所有节点，使其成为一个节点对
• 对于这个节点对，我们 遍历 图中的所有节点作为中继节点，看看能否使得这一对节点之间的距离更短
  1. 如果距离更短则更新这个距离到邻接矩阵
  2. 如果不能够更短则继续寻找

很显然，根据我加粗的文本能够看到，这是一个三重循环，所以 Floyd 算法的时间复杂度为 $O(n^3)$

具体的代码实现大概如下：

1
2
3
4
5
6

for relay in vertices:
    for src in vertices:
        for dest in vertices:
            newdis = distance[src.index, relay.index] + distance[relay.index, dest.index]
            if distance[src.index, dest.index] > newdis:
                distance[src.index, dest.index] = newdis

其中 distance 为邻接矩阵，vertices 为顶点集。

正确性证明

不知道有没有人和我才开始时有一样的问题：如果我们首先发现了 $u$ 到 $i$ 的最短路径，并且 $u \rightarrow v$ 这条直接路径更短，会不会导致 $u$ 到 $v$ 的最短路径计算出错呢？

实际上是不会的，Floyd 算法的核心思想是动态规划，而任何一个动态规划要想保证正确性需要有两个性质：

1. 无后效性/马尔可夫性 - 也就是上层问题的解不会影响子问题的解

   根据上面的状态转移方程我们就能够看出，$k$ 次节点的状态完全由 $k - 1$ 次转化而来，无后效性 得以保证

2. 最优子结构 - 也就是最优解的子解也是最优解

   图论中我们可以显而易见的得到一个定理 —— 最短路径的子路径仍然是最短路径，什么意思呢？

   假设从顶点 $u \rightarrow v$ 的最短路径是：$u \rightarrow x \rightarrow y \rightarrow z \rightarrow v$

   那么我们一定可以得到从 $u \rightarrow y$ 的最短路径是 $u \rightarrow x \rightarrow y$

   换句话说，如果某一条最短路径一定要经过一个中继节点，那么从源节点到中继节点的最短路径也是被确定的，这样就保证了 最优子结构

事实上，如果我们手动的模拟 Floyd 算法的过程，就会发现，如果经过某一个节点的距离比直接走的距离还要长，那么这个距离根本就不会更新；同样的，如果经过某 $n + 1$ 个节点的路径比 $n$ 个中继节点时短，该距离也不会更新。

路径重建

在运行完算法之后，我们仅仅得到了任意两点之间的最短 距离，而不是最短路径；如果我们想要得到路径，那么就需要在上面更新距离的同时更新最短路径。

我们可以在运行算法之前，保存一个路径映射（在 Python 中可以看作是字典）其中的元素是节点列表，并按照如下规则将其初始化：

1. 如果两个节点不相邻，则不添加
2. 如果两个节点相邻，则添加 [src, dest]

之后在更新最短距离时候，按照算法的思想，把从源节点到中继节点的路径拿出来，后面 extend 从中继节点到目标节点的路径即可。

适用性

Floyd 算法可以处理负权边，因为上面的状态转移方程并不限制两条边之间的权大小；但是图中不能够出现 负权环，这是因为当图中有负权值的环时，最短路径便失去了意义：因为我们只需要沿着负权值环不断循环，就能够得到一个 $-\infty$ 的路径。