【算法分析与设计】第16篇：全源最短路径与Floyd-Warshall动态规划

前两篇我们围绕单源最短路径展开了深入讨论Bellman-Ford能够处理负权边Dijkstra在非负权图上效率更高。现在将问题进一步升级——不再指定一个源点而是要求计算图中所有顶点对之间的最短距离。这就是全源最短路径问题。最直接的做法是对每个顶点运行一次单源最短路径算法。若图稀疏且边权非负运行 ∣V∣∣V∣ 次Dijkstra总复杂度 O(∣V∣⋅∣E∣log⁡∣V∣)O(∣V∣⋅∣E∣log∣V∣)若存在负权边则需运行 ∣V∣∣V∣ 次Bellman-Ford总复杂度高达 O(∣V∣2⋅∣E∣)O(∣V∣2⋅∣E∣)。这些方案可行但不够优雅。是否存在一个统一的算法一次性输出所有顶点对的最短距离Floyd-Warshall算法正是为此而生。一、问题形式化与动态规划建模给定带权有向图 G(V,E)G(V,E)V{1,2,…,n}V{1,2,…,n}边权 wijwij​ 可正可负。要求对所有顶点对 (i,j)(i,j) 计算最短距离 dijdij​。约定 dii0dii​0若 ii 无法到达 jj 则 dij∞dij​∞。Floyd-Warshall的核心思想是一条关于路径构成的观察一条从 ii 到 jj 的最短路径其中间顶点不含首尾 ii 和 jj均取自顶点集 {1,2,…,k}{1,2,…,k}。通过逐步扩大允许使用的中间顶点集合我们可以从较小的子问题递推到全局解答。形式化地定义状态 dij(k)dij(k)​ 为从顶点 ii 到顶点 jj且中间顶点仅取自集合 {1,2,…,k}{1,2,…,k} 的最短路径长度。这里 kk 的取值为 0,1,…,n0,1,…,nk0k0 表示不允许任何中间顶点路径仅由一条边构成或不存在。knkn 表示允许使用所有顶点作为中间顶点即全局最短路径。状态转移方程的推导基于一个二分支选择当中间顶点集合从 {1,…,k−1}{1,…,k−1} 扩充到 {1,…,k}{1,…,k} 时ii 到 jj 的最短路径是否经过新加入的顶点 kk不经过 kk则路径的全部中间顶点仍局限于 {1,…,k−1}{1,…,k−1}距离为 dij(k−1)dij(k−1)​。经过 kk则路径可分解为 i⇝k⇝ji⇝k⇝j 两段每段的中间顶点均取自 {1,…,k−1}{1,…,k−1}距离为 dik(k−1)dkj(k−1)dik(k−1)​dkj(k−1)​。二者取最小即得dij(k)min⁡(dij(k−1), dik(k−1)dkj(k−1))dij(k)​min(dij(k−1)​,dik(k−1)​dkj(k−1)​)边界条件dij(0)wijdij(0)​wij​若边存在dii(0)0dii(0)​0否则为 ∞∞。二、空间优化三维到二维的消去技巧上述递推需要维护三维数组 d[n1][n][n]d[n1][n][n]空间复杂度 Θ(n3)Θ(n3)。但仔细观察转移方程可以发现一个关键性质dij(k)dij(k)​ 仅依赖于 dij(k−1)dij(k−1)​、dik(k−1)dik(k−1)​ 和 dkj(k−1)dkj(k−1)​。而第三维 kk 实际上起到了“版本号”的作用。更重要的是dik(k−1)dik(k)dik(k−1)​dik(k)​ 和 dkj(k−1)dkj(k)dkj(k−1)​dkj(k)​——因为以 kk 为终点的路径若已经允许使用 kk 作为中间顶点无异于允许使用 {1,…,k−1}{1,…,k−1}终点 kk 本身不能用作中间顶点同理以 kk 为起点的路径亦然。因此在更新第 kk 轮时dd 矩阵的第 kk 行和第 kk 列的值不会因 kk 的增加而改变。这意味着我们可以原地更新仅用一个二维数组 d[n][n]d[n][n]外层循环 kk 从 11 到 nn中内层循环 ii 和 jj 遍历所有顶点对执行d[i][j]min⁡(d[i][j], d[i][k]d[k][j])d[i][j]min(d[i][j],d[i][k]d[k][j])算法的简洁程度令人惊讶——三重循环每层都是 nn 次迭代总时间复杂度 Θ(n3)Θ(n3)空间复杂度 Θ(n2)Θ(n2)。仅需几行代码便能解决全源最短路径问题。这个极简结构也使得Floyd-Warshall成为算法教学中动态规划的经典范例之一。三、负权边与负权环的处理Floyd-Warshall算法允许边权为负前提是图中不存在负权环。若存在可从 ii 到达的负权环则 ii 到环上任意顶点的距离应为 −∞−∞而非某个有限的数值。检测负权环的方法极其简单算法结束后检查对角线上是否存在 d[i][i]0d[i][i]0。d[i][i]d[i][i] 表示从 ii 出发回到 ii 的最短路径长度若为负则 ii 必定位于某个负权环之上。在实际应用中一旦检测到负权环的存在通常意味着模型本身存在缺陷例如差分约束系统不一致、套汇检测中发现盈利机会需回头审视建模假设。四、路径重构全源最短路径的输出不仅需要距离矩阵 DD还需记录路径本身。只需维护一个额外的前驱矩阵 pred[n][n]pred[n][n]初始化为pred[i][j]{i若 ij 或 wij≠∞NULL否则pred[i][j]{iNULL​若 ij 或 wij​∞否则​在松弛 d[i][j]d[i][k]d[k][j]d[i][j]d[i][k]d[k][j] 时同时更新 pred[i][j]←pred[k][j]pred[i][j]←pred[k][j]。最终通过递归查找即可重构 ii 到 jj 的完整最短路径。五、Johnson算法简述稀疏图上的更优方案对于稀疏图∣E∣≪∣V∣2∣E∣≪∣V∣2Θ(n3)Θ(n3) 的Floyd-Warshall并不经济。此时若存在负权边但无负权环Johnson算法提供了更优的选择。Johnson算法的核心技巧是重赋权为每个顶点 vv 分配一个势能 h(v)h(v)构造新的边权函数w^(u,v)w(u,v)h(u)−h(v)w^(u,v)w(u,v)h(u)−h(v)可以证明对任意顶点对 (i,j)(i,j)经过重赋权后所有路径的长度仅在原始长度的基础上加上了常数差 h(i)−h(j)h(i)−h(j)因此最短路径的结构保持不变。同时适当地选择 h(⋅)h(⋅) 可使所有 w^(u,v)≥0w^(u,v)≥0从而可以使用Dijkstra算法。具体地在原图中增加一个超级源点 ss连接至所有顶点且边权为 00运行一次Bellman-Ford算法求 ss 到各顶点的最短距离即令 h(v)δ(s,v)h(v)δ(s,v)。由三角不等式 δ(s,v)≤δ(s,u)w(u,v)δ(s,v)≤δ(s,u)w(u,v) 移项即得 w^(u,v)≥0w^(u,v)≥0。随后对每个顶点运行一次Dijkstra在重赋权后的图上再将结果还原为原始权值下的距离。Johnson算法的时间复杂度为 O(∣V∣⋅∣E∣log⁡∣V∣)O(∣V∣⋅∣E∣log∣V∣)在二叉堆Dijkstra下当 ∣E∣O(∣V∣)∣E∣O(∣V∣) 时仅为 O(∣V∣2log⁡∣V∣)O(∣V∣2log∣V∣)显著优于Floyd-Warshall的 Θ(∣V∣3)Θ(∣V∣3)。两者的适用边界清晰稠密图选Floyd-Warshall稀疏图选Johnson。六、小结与后续从Bellman-Ford到Dijkstra再到Floyd-Warshall与Johnson最短路径算法形成了一个完整的知识网络。它们共享松弛操作这一基本动作区别仅在于松弛的组织顺序与适用的权值条件。理解这个网络不仅是为了求解最短路径本身更是为了掌握算法设计中“利用问题结构性质换取效率提升”的核心思想。下一篇我们将暂时离开路径问题进入图论中另一座理论高峰——网络流。从最大流问题的定义出发以Ford-Fulkerson方法和最大流最小割定理为起点开启流网络这一全新领域。