Johnson算法

What · 是什么

Johnson 算法求任意两点间的全源最短路，O(VE log V)，在稀疏图上优于 Floyd 的 O(V³)，且支持负权边（不能有负环）。思路：加虚拟源点 0 向所有点连 0 权边，用 Bellman-Ford 求出各点势能 h(i)；把每条边 (u,v,w) 重新标记为 w'=w+h(u)-h(v)≥0，然后对每个点跑一遍 Dijkstra 求最短路，最后把势能差加回去。是『把负权图变成非负权图再利用 Dijkstra 的贪心优势』的经典势能技巧，也是最小费用流 SSP 里用 Dijkstra 的核心思想来源。

Why · 为什么

How · 实现

伪代码

def johnson(n, edges):
  # 虚拟源点 0
  h = bellman_ford(n+1, edges + [(n,i,0) for i in range(n)], n)[1]
  if 负环: return None
  # 重标号
  w'[u,v] = w[u,v] + h[u] - h[v]   # 全部 >=0
  adj' = 按 w' 建邻接表
  ans = [[0]*n for _ in range(n)]
  for s in range(n):
    d' = dijkstra(adj', s)
    for t in range(n):
      ans[s][t] = d'[t] - h[s] + h[t]
  return ans

Python 实现

import heapq


def _dijkstra(adj, s, n):
    INF = float('inf')
    dis = [INF] * n
    dis[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dis[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dis[v]:
                dis[v] = nd
                heapq.heappush(pq, (nd, v))
    return dis


def johnson(n, edges):
    """全源最短路(支持负权, 无负环). edges: [(u,v,w)].
    返回 dis 矩阵; 不可达为 float('inf'); 存在负环返回 None."""
    INF = float('inf')
    super_src = n
    super_edges = edges + [(super_src, i, 0) for i in range(n)]

    h = [INF] * (n + 1)
    h[super_src] = 0
    for _ in range(n):
        updated = False
        for u, v, w in super_edges:
            if h[u] != INF and h[u] + w < h[v]:
                h[v] = h[u] + w
                updated = True
        if not updated:
            break
    for u, v, w in super_edges:
        if h[u] != INF and h[u] + w < h[v]:
            return None  # 负环

    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        w2 = w + h[u] - h[v]
        if w2 < 0:
            w2 = 0  # 数值保护(理论上 w'>=0, 浮点/取整边界兜底)
        adj[u].append((v, w2))

    ans = [[INF] * n for _ in range(n)]
    for s in range(n):
        d2 = _dijkstra(adj, s, n)
        for t in range(n):
            if d2[t] != INF:
                ans[s][t] = d2[t] - h[s] + h[t]
            else:
                ans[s][t] = INF
    return ans


if __name__ == "__main__":
    # 带负权的稀疏图
    n = 4
    edges = [(0, 1, 3), (0, 2, -2), (1, 3, 2), (2, 3, 5), (2, 1, 1), (3, 1, -1)]
    ans = johnson(n, edges)
    assert ans is not None
    assert ans[0][3] == 1, ans[0]  # 0->2(-2)->1(1)->3(2) = 1
    assert ans[0] == [0, -1, -2, 1], ans[0]

    # 与 Floyd 交叉验证
    import random
    random.seed(41)
    for _ in range(200):
        n = random.randint(1, 7)
        edges = []
        for i in range(n):
            for j in range(n):
                if i != j and random.random() < 0.3:
                    edges.append((i, j, random.randint(-4, 7)))
        # Floyd 参考
        INF = float('inf')
        d = [[INF] * n for _ in range(n)]
        for i in range(n):
            d[i][i] = 0
        for u, v, w in edges:
            d[u][v] = min(d[u][v], w)
        for k in range(n):
            for i in range(n):
                if d[i][k] == INF:
                    continue
                for j in range(n):
                    if d[k][j] == INF:
                        continue
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        neg = any(d[i][i] < 0 for i in range(n))
        ans = johnson(n, edges)
        if neg:
            assert ans is None, (n, edges)
        else:
            assert ans is not None
            for i in range(n):
                for j in range(n):
                    a, b = ans[i][j], d[i][j]
                    if a == INF or b == INF:
                        assert a == b, (i, j, a, b)
                    else:
                        assert abs(a - b) < 1e-9, (i, j, a, b)

    # 负环
    assert johnson(3, [(0, 1, 1), (1, 2, -3), (2, 0, 1)]) is None
    print("All tests passed.")

易错点

• 忘记先判负环：Bellman-Ford 求 h 时若第 n 轮仍可松弛必须返回无解
• 重标号后忘记把 h 差加回去（ans = d' - h[s] + h[t]）
• 虚拟源点到所有点连 0 权边是必要的，否则 h 只覆盖从 0 可达部分
• n 次 Dijkstra 之间要复用邻接表，别重复建图
• h 数组用 INF 初始化，未从 0 达的点要处理

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/shortest-path/
• CP-Algorithms✓ https://cp-algorithms.com/graph/johnson.html
• 书籍✓ CPH ch13 pp133-142