Johnson 全源最短路算法

Johnson 算法是一种求解稀疏有向图中所有顶点对最短路径的算法,由 Donald B. Johnson 于 1977 年提出。它巧妙地结合了 Bellman-Ford 算法和 Dijkstra 算法,既能正确处理含负权边的图,又能在稀疏图上取得优于 Floyd-Warshall 的效率。

概述

全源最短路问题要求出图中每一对顶点间的最短距离。Floyd-Warshall 算法可以直接解决,复杂度为顶点数的三次方,与边数无关,对稀疏图并不划算。Johnson 算法的思路是:先把带负权的图重新赋权为等价的非负权图,再对每个顶点分别运行高效的 Dijkstra。

核心原理

算法的核心是重赋权技术。它先向图中加入一个虚拟源点,向所有原顶点连零权边,用 Bellman-Ford 求出该源点到每个顶点的距离 h(v);若此过程检测到负环则直接报告无解。

• 重赋权:把每条边 (u,v) 的权重 w(u,v) 改为 w(u,v) 加 h(u) 减 h(v),可证明新权重非负且不改变任意路径的相对长短。
• 逐点 Dijkstra:对重赋权后的非负图,以每个顶点为源跑一次 Dijkstra。
• 还原距离:把 Dijkstra 得到的距离减去 h(u) 加 h(v),即为原图中真实的最短距离。

应用场景

Johnson 算法适用于顶点对最短路查询频繁、图较稀疏且可能含负权边的场景,例如某些网络路由分析、运筹学中的成本流建模。其总复杂度约为顶点数乘边数再乘以对数因子,在稀疏图上优于 Floyd-Warshall。

常见问题

问:重赋权后为什么最短路不变?答:因为对一条从 s 到 t 的路径,所有中间顶点的 h 值都成对抵消,路径总权只多出 h(s) 减 h(t) 这一与路径无关的常数,所以最短路径的选择不受影响。

问:它能处理负环吗?答:不能求出含负环图的最短路,但第一步的 Bellman-Ford 会检测到负环并终止,从而正确地报告无解。