在图论的世界里，找到所有顶点对之间的最短路径是一个经典且极具挑战性的问题。我们之前已经探讨过 Floyd-Warshall 算法，虽然它逻辑简单且易于实现，但其 Θ(V³) 的时间复杂度在面对大规模稀疏图时显得力不从心。今天，我们将深入探讨 Johnson 算法——一种结合了 Bellman-Ford 和 Dijkstra 算法优势的混合策略。Johnson 算法不仅能处理带有负权边的图（只要没有负权环），还能在稀疏图中达到 O(V²log V + VE) 的高效性能。
在我们最近的几个涉及城市交通网络建模和复杂依赖关系分析的项目中，我们发现 Johnson 算法在处理稀疏图时表现出了惊人的优势。让我们一起来揭开它的神秘面纱，看看它是如何通过“重新赋权”的魔法，将一个棘手的问题转化为我们可以轻松解决的子问题的。
算法核心：为什么需要 Johnson 算法？
你可能会问，为什么我们不能直接对每个顶点运行 Dijkstra 算法？这确实是一个好问题。如果图中所有边的权重都是非负的，对每个顶点运行 Dijkstra 确实是更优的选择，总时间复杂度为 O(V (E + V) log V)。然而，现实世界的数据往往比理想模型复杂得多。在金融建模（处理负现金流）或某些网络协议的成本计算中，负权边是客观存在的。Dijkstra 算法的贪心策略在遇到负权边时会直接失效。
另一方面，Bellman-Ford 算法虽然能处理负权边，但其 O(VE) 的时间复杂度较高。如果我们对 V 个顶点都运行它，总复杂度将达到 O(V²E)，这在性能上是不可接受的。
Johnson 算法的核心思想是“重新赋权”。 我们的目标是将原图转换为一个所有边权均为非负的新图，且必须保证原有的最短路径结构不发生改变。一旦完成这一步，我们就可以放手使用高效的 Dijkstra 算法。
重新赋权的艺术：如何处理负权重？
简单的将所有边加上一个常数是行不通的，因为路径包含的边数不同，增加的总量也会不同，从而破坏路径的相对长度。Johnson 算法巧妙地引入了一个基于顶点的势能函数 h[v]。
我们将新边权重定义为：
w‘(u, v) = w(u, v) + h[u] – h[v]
这种变换的精妙之处在于，对于任意一条从 s 到 t 的路径，所有中间顶点的 h 值都会相互抵消，最终只剩下 h[s] – h[t]。这意味着，s 到 t 之间的所有路径都增加了相同的量，因此最短路径依然是原来的那条最短路径。
Johnson 算法的完整工作流程
为了计算这个神奇的 h[] 值，我们执行以下步骤：
- 添加虚拟源点：我们在图中引入一个新的虚拟顶点，并将其与图中所有其他顶点相连，设这些边的权重为 0。
- 运行 Bellman-Ford：以这个新顶点为源点运行 Bellman-Ford 算法。计算出的距离 h[v] 就是我们需要的顶点势能。如果检测到负权环，算法终止（因为此时最短路径无定义）。
- 重新赋权：利用上述公式修改所有边的权重。
- 运行 Dijkstra：移除虚拟源点，对图中每个顶点作为源点运行 Dijkstra 算法。
#### 证明：为什么新权重是非负的？
由于 h[] 是从虚拟源点出发的最短路径距离，根据三角不等式，对于任意边 (u, v)，我们有：
h[v] <= h[u] + w(u, v)
移项可得：
w(u, v) + h[u] – h[v] >= 0
这正是我们需要的新权重 w‘。数学的严谨性在这里保证了算法的健壮性。
2026年视角：现代工程化实现与最佳实践
在算法教科书上，故事往往到这里就结束了。但在 2026 年的实际软件开发中，如何实现和如何维护这段代码同样重要。让我们看看如何将这一经典算法融入现代开发范式。
#### 生产级代码实现（Python 3.10+）
在我们的技术栈中，我们倾向于使用类型提示和清晰的文档字符串，以便与 AI 辅助工具（如 GitHub Copilot 或 Cursor）更好地协作。
import heapq
from typing import List, Dict, Tuple
class Graph:
def __init__(self, vertices: int):
self.V = vertices
self.adj = [[] for _ in range(vertices)]
def add_edge(self, u: int, v: int, weight: int):
"""添加有向边，支持负权重"""
self.adj[u].append((v, weight))
def _bellman_ford_reweighting(self, src: int) -> List[float]:
"""
使用 Bellman-Ford 计算势能函数 h[]。
如果检测到负权环，抛出 ValueError。
"""
dist = [float("Inf")] * (self.V + 1) # +1 for the dummy node
dist[src] = 0
# 松弛所有边 V 次（最后一次用于检测负环）
# 我们需要隐式地处理添加的那个虚拟源点，或者直接修改图结构
# 这里为了演示清晰，我们假设图已经被修改（在实际应用中建议不要污染原Graph对象）
# 实际上，我们通常传入临时的边列表
return dist # 简化版示意
def johnsons_algorithm(self) -> Dict[Tuple[int, int], int]:
# 1. 创建包含虚拟源点的临时边列表
edges = []
for u in range(self.V):
for v, w in self.adj[u]:
edges.append((u, v, w))
# 添加从虚拟源点 self.V 到 u 的边，权重为 0
edges.append((self.V, u, 0))
# 2. 运行 Bellman-Ford 计算h[]
dist = [float("Inf")] * (self.V + 1)
dist[self.V] = 0
for _ in range(self.V):
updated = False
for u, v, w in edges:
if dist[u] != float("Inf") and dist[v] > dist[u] + w:
dist[v] = dist[u] + w
updated = True
if not updated:
break
# 检查负权环
h = dist[:-1] # 去掉虚拟源点的距离
for u, v, w in edges:
if dist[u] != float("Inf") and dist[v] > dist[u] + w:
raise ValueError("图中包含负权重环，无法计算最短路径")
# 3. 重新赋权并运行 Dijkstra
all_pairs_shortest_paths = {}
for u in range(self.V):
# Dijkstra
min_heap = [(0, u)]
d_dist = {i: float("Inf") for i in range(self.V)}
d_dist[u] = 0
while min_heap:
current_dist, u_node = heapq.heappop(min_heap)
if current_dist > d_dist[u_node]:
continue
for v, weight in self.adj[u_node]:
# 关键：使用重新赋权后的权重 w‘ = w + h[u] - h[v]
new_weight = weight + h[u_node] - h[v]
if d_dist[v] > d_dist[u_node] + new_weight:
d_dist[v] = d_dist[u_node] + new_weight
heapq.heappush(min_heap, (d_dist[v], v))
# 修正结果：因为我们在 Dijkstra 中计算的是 w‘ 的距离，需要还原
# 实际距离 = d_dist[v] - h[u] + h[v]
for v in range(self.V):
if d_dist[v] != float("Inf"):
# 实际存储的应该是原始路径长度
# 这里的数学推导：Distance‘(u, v) = Distance(u, v) + h[u] - h[v]
# 所以 Distance(u, v) = Distance‘(u, v) - h[u] + h[v]
all_pairs_shortest_paths[(u, v)] = d_dist[v] - h[u] + h[v]
return all_pairs_shortest_paths
现代开发中的决策与陷阱
在我们最近的一个微服务路由优化项目中，我们面临一个关键的决策：是使用 Floyd-Warshall 还是 Johnson 算法？
什么时候选择 Johnson 算法？
当你的图是稀疏图（E 远小于 V²）时，Johnson 算法通常是更好的选择。在我们的项目中，服务节点虽然有数百个，但每个服务的依赖（边）通常不超过几十个，这完全符合稀疏图的定义。此时 O(V² log V + VE) 的性能将显著优于 O(V³)。
常见陷阱与调试技巧
- 整数溢出：在重新赋权过程中，如果 h[u] 很大而 w(u, v) 很小，加法可能会导致数值溢出。在现代 Python 中这不是问题，但在 C++ 或 Rust 中，建议使用
long long类型。 - 无穷大的比较：在处理非连通图时，需要注意
Inf的减法操作（在结果修正步骤中）。如果 h[u] 或 h[v] 是无穷大，说明该点不可达，应跳过计算。 - 性能监控：在 2026 年的云原生环境下，我们不仅要看算法的时间复杂度，还要看空间局部性。Dijkstra 算法使用的优先队列（通常是最小堆）会产生随机的内存访问模式，这对 CPU 缓存不友好。如果你的图非常巨大，考虑使用基于数组的 Dijkstra 变体或更高级的层级图（Hierarchical Graph）技术。
AI 辅助开发与未来展望
随着 Agentic AI 的兴起，编写算法代码的方式也在发生变化。现在，我们可以让 AI 帮我们生成单元测试，特别是针对边界情况（如全负权图、非连通图）的测试用例。
Vibe Coding（氛围编程）实践：当我们使用 Cursor 或 Windsurf 等现代 IDE 时，我们不再只是盯着代码行。我们会向 AI 描述意图：“我们需要一个图类，支持添加边，并且能处理负权重。” 然后，由 AI 来处理繁琐的样板代码。我们作为开发者，更多地关注算法的正确性验证和逻辑的修正。
例如，在调试上述代码的 INLINECODE32468241 还原逻辑时，我发现直接使用简单的减法可能会导致精度丢失（如果是浮点数）。通过与 AI 结对编程，我们迅速定位到必须先判断节点是否可达（INLINECODE6996cc66），再进行算术操作，从而避免了 NaN 的传播。
总结
Johnson 算法是算法工程中的一个杰作，它完美地展示了如何通过组合简单的子程序来解决复杂问题。虽然在 GPU 加速或特定的硬件加速场景下，Floyd-Warshall 的动态规划可能仍有优势，但在通用的 CPU 环境和稀疏图场景下，Johnson 算法依然是 2026 年乃至未来几年的首选方案。
希望这篇文章不仅帮助你理解了算法原理，还能为你的实际工程开发提供参考。如果你在实施过程中遇到任何问题，欢迎随时与我们交流。