跳转到内容
← 返回算法
图算法计算机科学 · 图论 · 最短路径约 26 分钟阅读

Floyd-Warshall 算法

Floyd-Warshall Algorithm

1962 年，两位研究者几乎同时发表了全对最短路径算法。Robert Floyd 在 Communications of the ACM 上发表了"Algorithm 97: Shortest Path"；Stephen Warshall 的先前工作（1962 年，针对图的传递闭包）提供了相同的矩阵递推框架。因此，这个…

Floyd-Warshall全对最短路动态规划传递闭包

1962 年，两位研究者几乎同时发表了全对最短路径算法。Robert Floyd 在 Communications of the ACM 上发表了"Algorithm 97: Shortest Path"；Stephen Warshall 的先前工作（1962 年，针对图的传递闭包）提供了相同的矩阵递推框架。因此，这个算法通常称为 Floyd-Warshall。Bernard Roy 在 1959 年也独立发现了类似方法（在法国期刊发表，在英语世界较晚被关注）。

三行核心代码，三重循环，O(V3)O(V^3) 时间——Floyd-Warshall 是最简洁的图算法之一，同时解决了所有节点对之间的最短路径问题。而且，如后文所述，六十多年后它的 O(V3)O(V^3) 在理论上仍然几乎无法被真正超越。

问题：所有节点对最短路径

给定：有向加权图 $G = (V, E)$，顶点集 V={1,2,…,n}V = \{1, 2, \ldots, n\}，边权矩阵 $W$（$W[i][j]$ 为从 $i$ 到 $j$ 的直接边权，若无直接边则为 ∞\infty，对角线为 0）。

求：所有节点对 $(i, j)$ 之间的最短路径长度矩阵 $D$，其中 $D[i][j]$ 是从 $i$ 到 $j$ 的最短路径长度。

若用 Dijkstra 解决，对每个源节点运行一次，总时间 O(V⋅(V+E)log⁡V)O(V \cdot (V + E) \log V)——对稠密图（E=O(V2)E = O(V^2)）是 O(V3log⁡V)O(V^3 \log V)。Floyd-Warshall 用 O(V3)O(V^3) 就能搞定，且常数小，实现极简。

核心思想：中间节点的动态规划

关键问题重构：从 $i$ 到 $j$ 的最短路径，其中间节点只能从 {1,2,…,k}\{1, 2, \ldots, k\} 中选取。

状态：d(k)(i,j)d^{(k)}(i, j) = 只使用 {1,2,…,k}\{1, 2, \ldots, k\} 作为中间节点时，$i$ 到 $j$ 的最短路径长度。

初始：d(0)(i,j)=W[i][j]d^{(0)}(i, j) = W[i][j]（不用任何中间节点，只能用直接边）。

递推：

d(k)(i,j)=min⁡(d(k−1)(i,j), d(k−1)(i,k)+d(k−1)(k,j))d^{(k)}(i, j) = \min\left(d^{(k-1)}(i, j),\ d^{(k-1)}(i, k) + d^{(k-1)}(k, j)\right)

直觉：考虑加入节点 $k$ 作为可能的中间节点后，$i$ 到 $j$ 的最短路要么不经过 $k$（仍是 d(k−1)(i,j)d^{(k-1)}(i, j)），要么经过 $k$（$i$ 到 $k$ 的最短路 + $k$ 到 $j$ 的最短路）。最终 d(n)(i,j)d^{(n)}(i, j) 就是使用所有节点作为中间节点时的最短路径——即真正的全局最短路径。

算法代码：三行核心

python
# 初始化 dist 矩阵为邻接矩阵（无直接边为 inf，对角线为 0）
def floyd_warshall(dist, n):
    for k in range(n):            # 中间节点
        for i in range(n):        # 起点
            for j in range(n):    # 终点
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist
```

三重嵌套循环，每层遍历所有节点，时间 O(V3)O(V^3)，空间 O(V2)O(V^2)（矩阵）。这里 $k$ 的循环必须在最外层——这是正确性的关键，后文会给出一个把 $k$ 放内层就出错的 4 节点反例。

手算一遍：4 节点图的五张矩阵快照

下面这张图有 4 个节点、6 条边，其中一条负权。全部 D(0)D^{(0)} 到 D(4)D^{(4)} 都列出来，读者可以逐格复算。

边与权重：1→21\to2 = 5，1→41\to4 = 10，2→32\to3 = 3，3→13\to1 = 4，3→43\to4 = 1，4→24\to2 = −2。

先确认没有负权环：三条有向环 1→2→3→1=121\to2\to3\to1 = 12、2→3→4→2=3+1−2=22\to3\to4\to2 = 3+1-2 = 2、1→4→2→3→1=10−2+3+4=151\to4\to2\to3\to1 = 10-2+3+4 = 15，全为正。

D(0)D^{(0)}（= 邻接矩阵，不许用任何中间节点）

text
       1     2     3     4
1      0     5     ∞    10
2      ∞     0     3     ∞
3      4     ∞     0     1
4      ∞    −2     ∞     0
```

$k=1$：允许经过节点 1。要用 1 当跳板，就必须先能到达 1；而第 1 列里只有 $d(3,1)=4$ 是有限的，所以只有第 3 行会变。$d(3,2)$：原本 ∞，现在 3→1→2=4+5=93\to1\to2 = 4+5 = 9。

text
       1     2     3     4
1      0     5     ∞    10
2      ∞     0     3     ∞
3      4   [ 9]    0     1
4      ∞    −2     ∞     0
```

$k=2$：允许经过 {1,2}\{1,2\}。第 2 列非无穷的是 $d(1,2)=5$、$d(3,2)=9$、$d(4,2)=-2$；第 2 行只有 $d(2,3)=3$ 可用。于是 $d(1,3) = 5+3 = 8$，$d(4,3) = -2+3 = 1$。

text
       1     2     3     4
1      0     5   [ 8]   10
2      ∞     0     3     ∞
3      4     9     0     1
4      ∞    −2   [ 1]    0
```

$k=3$：允许经过 {1,2,3}\{1,2,3\}。第 3 行是 $(4, 9, 0, 1)$，第 3 列是 $(8, 3, 0, 1)$。这一轮收获最多：

  • $d(1,4)$：1→ ⁣⋯ ⁣→3→4=8+1=9<101\to\!\cdots\!\to 3 \to 4 = 8 + 1 = 9 < 10（原来的直连边被绕路打败了）
  • $d(2,1)$：2→3→1=3+4=72\to3\to1 = 3 + 4 = 7（从 ∞ 变成有限）
  • $d(2,4)$：2→3→4=3+1=42\to3\to4 = 3 + 1 = 4
  • $d(4,1)$：4→ ⁣⋯ ⁣→3→1=1+4=54\to\!\cdots\!\to3\to1 = 1 + 4 = 5
text
       1     2     3     4
1      0     5     8   [ 9]
2    [ 7]    0     3   [ 4]
3      4     9     0     1
4    [ 5]   −2     1     0
```

$k=4$：允许经过全部节点。第 4 行 $(5, -2, 1, 0)$，第 4 列 $(9, 4, 1, 0)$。唯一的改进是 $d(3,2)$：3→4→2=1+(−2)=−13\to4\to2 = 1 + (-2) = -1，把 $k=1$ 那轮算出的 9 覆盖掉。

text
       1     2     3     4
1      0     5     8     9
2      7     0     3     4
3      4  [ −1]    0     1
4      5    −2     1     0
```

这张终局矩阵最该注意的是第 3 行：$d(3,2)$ 在 $k=1$ 时被填成 9（走 3→1→23\to1\to2），到 $k=4$ 才被 −1 取代（走 3→4→23\to4\to2）。DP 的中间结果不是"逐渐变准"，而是"在受限条件下都是准的"——d(1)(3,2)=9d^{(1)}(3,2)=9 并不是错误答案，它是"只许经过节点 1 时"的正确答案。这个区别是理解 Floyd-Warshall 正确性证明的全部。

顺手验两格：$d(1,4)=9$ 走 1→2→3→4=5+3+11\to2\to3\to4 = 5+3+1；$d(4,1)=5$ 走 4→2→3→1=−2+3+44\to2\to3\to1 = -2+3+4。对角线全为 0，说明没有负权环。

为什么 $k$ 必须在最外层

"$k$ 放内层会错"这句话在教程里到处都是，但很少有人给出一个错的具体数字。下面这张 4 节点图就够了。

边与权重：1→21\to2 = 10，1→41\to4 = 1，4→34\to3 = 1，3→23\to2 = 1。真实的 $d(1,2)$ 应该是 1→4→3→2=31\to4\to3\to2 = 3，而不是那条 10 的直连边。

text
       1     2     3     4
1      0    10     ∞     1
2      ∞     0     ∞     ∞
3      ∞     1     0     ∞
4      ∞     ∞     1     0
```

正确版本（$k$ 最外层）：$k=1,2$ 无事发生；$k=3$ 时 $d(4,2) = d(4,3)+d(3,2) = 1+1 = 2$；$k=4$ 时 $d(1,2) = d(1,4)+d(4,2) = 1+2 = 3$ ✅。信息按"中间节点集合逐步放宽"的节奏两级接力完成。

错误版本（$k$ 最内层）：

python
for i in range(n):
    for j in range(n):
        for k in range(n):          # ← k 在最内层
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
```

这时 $(i,j)$ 每一对只被处理一次，处理完就定稿。按 $i$、$j$ 递增的顺序，$(1,2)$ 是第二个被处理的格子：

尝试的 $k$$d(1,k) + d(k,2)$结果
1$0 + 10$10
2$10 + 0$10
3∞+1\infty + 1∞
41+∞1 + \infty∞

取最小值仍是 10。而 $d(4,2)$ 要到 $(i,j)=(4,2)$ 才被算成 2，$d(1,3)$ 要到 $(1,3)$ 才被算成 2——都在 $(1,2)$ 定稿之后，而 $(1,2)$ 永远不会被回访。最终输出 $d(1,2) = 10$，真值 3，错了 3.3 倍。

根因一句话：$k$ 在最外层时，第 $k$ 轮读到的所有值都已经是"中间节点 ⊆{1..k−1}\subseteq \{1..k-1\}"下的完整答案，这个前提让递推式成立；$k$ 在内层时，读到的是一堆处于不同完成度的半成品。

顺便说一个有意思的补丁：把错误版本的整个三重循环重复跑 $n$ 遍，它会收敛到正确答案——因为那退化成了朴素的反复松弛，代价是 O(V4)O(V^4)。所以 $k$ 放外层省下的不是正确性，是一整个数量级。

路径重建

除了最短距离，通常还需要重建具体路径。引入前驱矩阵（Predecessor Matrix） $P$：

  • 初始：若 i≠ji \neq j 且存在直接边，$P[i][j] = i$；否则 P[i][j]=NoneP[i][j] = \text{None}
  • 更新：若 $d[i][k] + d[k][j] < d[i][j]$，则 $P[i][j] = P[k][j]$（经过 $k$ 的路径，$j$ 的前驱改为从 $k$ 到 $j$ 的路径上 $j$ 的前驱）

重建路径：从 $j$ 出发，反复查 P[⋅][j]P[\cdot][j] 直到回到 $i$。

负权环检测

Floyd-Warshall 也可以检测负权环：若计算后某对角线元素 $d[i][i] < 0$，则说明存在负权环经过节点 $i$。初始对角线全为 0，若某节点 $i$ 存在负权回路，则 $d[i][i]$ 会在算法中被更新为负值。

但要注意检测的顺序：负权环一旦存在，矩阵里的其他格子就不再有意义。原地更新会让负对角线继续参与后续松弛，把负值沿着可达关系扩散出去，得到一堆既不是最短路、也不是 −∞-\infty 的垃圾。正确用法是先扫一遍对角线，确认全部非负，再去读任何一个 $d[i][j]$。想进一步知道"哪些点对之间的最短路是 −∞-\infty"，标准做法是：对每个满足 $d[k][k] < 0$ 的 $k$，把所有能到 $k$ 又能从 $k$ 出来的点对 $(i,j)$ 标成 −∞-\infty。

传递闭包：Floyd-Warshall 的布尔版本

若边权为 1（表示"有连接"），Floyd-Warshall 退化为计算图的传递闭包（Transitive Closure）：

t(k)(i,j)=t(k−1)(i,j)∨(t(k−1)(i,k)∧t(k−1)(k,j))t^{(k)}(i, j) = t^{(k-1)}(i, j) \vee \left(t^{(k-1)}(i, k) \wedge t^{(k-1)}(k, j)\right)

Warshall 1962 年的原始论文正是针对传递闭包的，这也是算法名字包含 Warshall 的原因。传递闭包的应用包括可达性分析（网页是否可从首页到达？）、数据库中的递归查询、程序依赖分析。

布尔版本有一个非常实在的实现红利：∨\vee 和 ∧\wedge 可以按位并行。把每一行压成一串机器字（bitset），内层的 $j$ 循环就变成整行的按位或，一条 64 位指令处理 64 个 $j$，用 AVX-512 更是 512 个。O(V3)O(V^3) 于是变成 O(V3/w)O(V^3 / w)，$w$ 是字长——渐进复杂度没变，实际速度差了一到两个数量级。这也是为什么图数据库里的可达性预计算至今仍在用这个 1962 年的算法。

与矩阵乘法的关系：$(\min, +)$ 半环

Floyd-Warshall 与线性代数的关系不是类比，是等式。定义两个矩阵在 (min⁡,+)(\min, +) 半环（也叫热带半环，tropical semiring）下的乘法：

(A⊗B)[i][j]=min⁡k(A[i][k]+B[k][j])(A \otimes B)[i][j] = \min_k \big(A[i][k] + B[k][j]\big)

把普通矩阵乘法里的 ∑\sum 换成 min⁡\min、×\times 换成 $+$，就是它。于是 W⊗2W^{\otimes 2} 的第 $(i,j)$ 项正是"至多 2 条边"的最短路，W⊗mW^{\otimes m} 是"至多 $m$ 条边"的最短路（对角线取 0 保证"至多"而非"恰好"）。无负权环时最短路不超过 $V-1$ 条边，所以

D=W⊗(V−1)D = W^{\otimes (V-1)}

这给出一条完全不同的算法路线：反复平方。W⊗2→W⊗4→W⊗8→⋯W^{\otimes 2} \to W^{\otimes 4} \to W^{\otimes 8} \to \cdots，⌈log⁡2(V−1)⌉\lceil \log_2 (V-1) \rceil 次乘法就够，总时间 O(V3log⁡V)O(V^3 \log V)。比它更好的正是 Floyd-Warshall 的 O(V3)O(V^3)——Floyd-Warshall 的实质，就是用"逐个放开中间节点"这个巧妙的分解，省掉了那个 log⁡V\log V。

自然会问：矩阵乘法早就有 Strassen 的 O(n2.81)O(n^{2.81}) 乃至 O(n2.37)O(n^{2.37}) 了，为什么不搬过来？

因为这些快速算法全部依赖减法。Strassen 的七次递归乘法之所以能拼出八个子块，靠的是加加减减互相抵消；Coppersmith-Winograd 一路的张量方法同理。而 (min⁡,+)(\min, +) 只是一个半环——min⁡\min 没有逆运算，你无法"减掉一个 min"。缺了加法逆元，整套代数消去技巧就失效了。

已知的最好结果是 Ryan Williams 在 2014 年（STOC）给出的

n32Ω(log⁡n)\frac{n^3}{2^{\Omega(\sqrt{\log n})}}

用的工具是电路复杂度里的 Razborov-Smolensky 多项式近似。注意这只是次立方，不是真次立方：分母是超对数但亚多项式的，永远达不到 O(n3−ϵ)O(n^{3-\epsilon}) 那种形式的加速。

而"真次立方不存在"正是复杂度理论里著名的 APSP 猜想。Virginia Vassilevska Williams 与 Ryan Williams 在 2010 年（FOCS，期刊版 JACM 2018）证明了一批问题与 APSP 次立方等价——负权三角形检测、最小权三角形、度量性验证、次短路、替代路径等等。任何一个被真次立方地解决，全部一起被解决；反之，任何一个有立方下界，APSP 就有立方下界。

这给了 1962 年的 Floyd-Warshall 一个罕见的地位：在亚多项式因子的意义上，它已经是最优的，而且要证明它不是最优，需要推翻一个学界普遍相信的猜想。

实际应用场景

小规模稠密图的全对最短路是它的主场：节点数 V≤500V \leq 500 时，V3≈1.25×108V^3 \approx 1.25 \times 10^8 次内层操作，毫秒到几十毫秒级完成；$V = 1000$ 时是 10910^9，秒级；$V = 2000$ 时是 8×1098 \times 10^9。记住这个比例关系比记住绝对时间有用——$V$ 翻一倍，代价是 8 倍，所以"能不能用 Floyd-Warshall"这个问题几乎总能靠 $V$ 一眼判断。

货币汇率套利检测：设汇率图中 $W[i][j] = -\log(\text{汇率}_{i \to j})$，负权环对应套利机会，Floyd-Warshall 检测负对角线。相比 Bellman-Ford，它一次给出"哪些币种之间存在套利闭环"的完整答案。

关系代数与图数据库：计算可达性或最短路径，尤其在小型社交网络分析和依赖图分析中；上文那个 bitset 优化让传递闭包在这些场景里非常便宜。

网络与图形学：部分网络路由协议实现用 Floyd-Warshall 维护全对路由表；关节动画系统用它计算骨骼节点间的运动约束传播。这两类场景的共同点是节点数固定且不大（几十到几百），而查询极其频繁——预处理一次 O(V3)O(V^3)、之后每次查询 $O(1)$，这个交易在查询密集的系统里非常划算。

常数因子：为什么它在小图上打得过 $V$ 次 Dijkstra

O(V3)O(V^3) 对 O(VElog⁡V)O(V E \log V)，在稀疏图上后者渐进更优。但实际的交叉点比渐进分析暗示的位置高得多，原因全在内存访问模式上。

看最内层那个 $j$ 循环（矩阵按行主序存储）：

c
for (int j = 0; j < n; j++)
    d[i][j] = min(d[i][j], d_ik + d[k][j]);   // d_ik = d[i][k] 是循环不变量
```
  • d[i][k] 与 $j$ 无关，编译器直接提到寄存器里，整个内层循环只读一次。
  • d[k][j] 和 d[i][j] 都是连续、单位步长的访问：两条流式读 + 一条流式写，硬件预取器完美命中。
  • 循环体是 min(a, b + c)，没有分支、没有间接寻址，可以直接向量化——AVX2 下一条 vpaddd 加一条 vpminsd 同时处理 8 个 int32。

对比 $V$ 次 Dijkstra：邻接表是指针追逐，二叉堆的上浮下沉是随机访问加不可预测的分支，每次 decrease-key 都可能是一次缓存缺失。同样数量级的"操作数"，一边是流水线满载的向量运算，一边是充满停顿的指针跳转。这就是那个"常数小"的具体含义。

这个优势在矩阵装不下缓存时会打折。500×500 的 int32 矩阵是 1 MB，能待在 L2；5000×5000 是 100 MB，哪一级缓存都装不下，每一轮 $k$ 都要把整个矩阵从内存重新拉一遍。Venkataraman、Sahni 与 Mukhopadhyaya 在 2003 年提出的分块（blocked）Floyd-Warshall 就是解这个的：把矩阵切成能放进缓存的小块，按块做递推，让每块数据被载入后被充分复用。他们在 Sun Ultra Enterprise 4000/5000 上测得相对朴素实现 1.6 到 1.9 倍的加速（ACM JEA 8, 2003）。

该记住的判断：当一个算法的渐进复杂度已经在亚多项式意义上触到最优时，剩下能改进的全部空间都在内存层次里。Floyd-Warshall 六十年来的实际提速，几乎全部来自 bitset、分块、SIMD 与 GPU，而不是更聪明的递推。

与 Johnson 算法的对比

若图稀疏（E≪V2E \ll V^2）且需要全对最短路，Johnson 算法（Donald Johnson，1977）更高效：先用 Bellman-Ford 对所有边进行重新加权（Reweighting），消除负权边；再对每个节点运行一次 Dijkstra。总时间 O(V2log⁡V+VE)O(V^2 \log V + VE)——在稀疏图上远优于 O(V3)O(V^3)。

重新加权技巧的核心：引入虚拟源节点连接所有节点（边权 0），用 Bellman-Ford 求虚拟源到各节点的距离 $h$，将边 $(u,v)$ 的权重改为 $w(u,v) + h(u) - h(v)$——这保证新权重非负（三角不等式 h(v)≤h(u)+w(u,v)h(v) \le h(u) + w(u,v) 直接给出），且不改变最短路径的相对顺序（沿任一条 i→ji \to j 的路径，所有中间的 $h$ 项两两抵消，总长只差一个与路径无关的常数 $h(i) - h(j)$）。

算法时间复杂度适用场景
Floyd-WarshallO(V3)O(V^3)小稠密图，代码简单
JohnsonO(V2log⁡V+VE)O(V^2 \log V + VE)大稀疏图（可能有负权）
$V$ 次 DijkstraO(VElog⁡V)O(VE \log V)无负权稀疏图

空间优化的微妙点

Floyd-Warshall 可以原地（in-place）更新同一矩阵而不是维护 d(k)d^{(k)} 和 d(k−1)d^{(k-1)} 两个矩阵。这是因为在更新 $d[i][j]$ 时，即使 $d[i][k]$ 或 $d[k][j]$ 已被当前轮更新，结果仍正确。

原因可以说得很干净：第 $k$ 轮里被提前更新的只可能是 $d[i][k]$ 与 $d[k][j]$ 这两类值，而它们的更新形如 d[i][k]←d[i][k]+d[k][k]d[i][k] \leftarrow d[i][k] + d[k][k]。无负权环时 $d[k][k] = 0$，所以这两个值在第 $k$ 轮内根本不会变——读到新值和旧值是同一件事。形式证明见 CLRS 课后练习 23.1-4。

这条性质是免费的，但它有一个前提被藏起来了：它依赖 $d[k][k] = 0$，也就是依赖无负权环。有负权环时原地版本会给出上一节说的那种垃圾——这也是为什么"先查对角线"不是可选的卫生习惯，而是原地实现的正确性条件。

跨域连接

  • 线性代数：把加法换成取小、乘法换成相加，最短路就是矩阵在热带半环上的幂，全对最短路即 $W$ 的 $V-1$ 次幂。这个视角还解释了一个否定结果：Strassen 一路的快速矩阵乘法全部依赖减法做代数消去，而取小运算没有逆元，整套技巧搬不过来。半环缺什么，算法就少一条路。
  • P 与 NP：全对最短路的立方界至今只被压掉一个亚多项式因子，而"真正次立方"被证明与一批问题彼此等价——负权三角形检测、最小权三角形、次短路等等。任何一个被真次立方解决，全部一起被解决。这类细粒度等价把"某个具体算法是不是最优"从直觉问题变成了可以下注的猜想。
  • 一般均衡：投入产出分析里的莱昂惕夫逆矩阵是幂级数求和，回答"最终需求多一单位，各部门总产出各要多多少"。它与传递闭包是同一个闭包运算，只是半环从取小加法换成普通加乘。因此两者共享同一条性质：一次预处理买下之后无限次查询，而稀疏程度决定这笔预处理值不值。
  • 计算语言学：上下文无关文法的表格分析填的也是一张三角矩阵——"哪些非终结符能推出这一段"，递推同样形如"左半段的结果与右半段的结果做一次合成"。换掉的只是半环：取小加法变成集合并与规则拼接。看清这点，句法分析与最短路同为立方复杂度就不再是巧合。
  • 数据库索引与查询优化：可达性预计算是递归查询的常见加速手段，而布尔版本的三重循环可以按位并行——把每行压成机器字，内层循环变成整行按位或。渐进复杂度一点没变，实际速度差一到两个数量级。这也给出该不该预计算的判据：图静态、查询频繁时，一次立方换无数次常数总是划算的。

参考文献

  • Floyd, R.W. "Algorithm 97: Shortest Path." Communications of the ACM 5(6), 1962.
  • Warshall, S. "A Theorem on Boolean Matrices." Journal of the ACM 9(1), 1962.
  • Johnson, D.B. "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1977.
  • Venkataraman, G., Sahni, S. & Mukhopadhyaya, S. "A Blocked All-Pairs Shortest-Paths Algorithm." ACM Journal of Experimental Algorithmics 8, 2003. DOI 10.1145/996546.996553.
  • Williams, R. "Faster All-Pairs Shortest Paths via Circuit Complexity." STOC 2014, 664–673.（期刊版 SIAM Journal on Computing）
  • Vassilevska Williams, V. & Williams, R. "Subcubic Equivalences between Path, Matrix and Triangle Problems." FOCS 2010, 645–654.（期刊版 Journal of the ACM 65(5), 2018）
  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022.（第 23 章 All-Pairs Shortest Paths）

延伸阅读

  • Maclagan, D. & Sturmfels, B. Introduction to Tropical Geometry. AMS, 2015.（(min⁡,+)(\min,+) 半环的系统介绍）
  • Vassilevska Williams, V. "On Some Fine-Grained Questions in Algorithms and Complexity." Proceedings of the ICM 2018, vol. 3, 3431–3472. World Scientific.（APSP 猜想及其等价问题族的入口综述）
  • Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011.（第 4 章图算法，含实现细节与实验）