算法（H）笔记——全源最短路

所有点对最短路径

矩阵快速幂

需要没有负环路

\(\theta(n^3lgn)\)

Floyd-Warshall

\(\theta(n^3)\)

前驱矩阵\(\pi_{ij}^{n}\)通过递归算出来后，假设查出来i到j路径上j的前驱是b，则递归查询\(\pi_{ib}^{n}\)

如果是从D推导pi，就是遍历，寻找\[d_{ij} = d_{ik} + w_{kj}\]

# 伪代码实现
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j or d[i][j] == float('inf'):
            pi[i][j] = "NIL"
        else:
            # 寻找满足 d[i][j] == d[i][k] + w[k][j] 的那个 k
            for k in range(1, n + 1):
                if k != j and w[k][j] != float('inf'): 
                    if d[i][j] == d[i][k] + w[k][j]:
                        pi[i][j] = k
                        break # 找到一个合法的前驱即可

传递闭包：算法改成

\[t_{ij}^{(k)} = t_{ij}^{(k-1)} \vee (t_{ik}^{(k-1)} \wedge t_{kj}^{(k-1)})\]

Johnson 算法

Johnson 算法用于求所有点对最短路径。

\(O(V^2lgV+VE)\)

它的主要特点是：

• 可以处理带负权边的图。
• 不能处理从源点可达的负权环。
• 适合稀疏图。
• 思路是先用 Bellman-Ford 重新赋权，再对每个点运行 Dijkstra。

课堂备注：由于 Dijkstra 的性质，可以针对某个源点求到其他点的最短路；相比之下，Floyd-Warshall 通常是整体地求出所有点对最短路径。因此 Johnson 算法的优势需要结合稀疏图和稠密图来区分。

核心思想

Johnson 算法先给图增加一个新源点 \(s\)，并从 \(s\) 向原图中每个点连一条权重为 \(0\) 的边。

然后用 Bellman-Ford 计算从 \(s\) 到每个点的最短路径权重，得到势函数 \(h(v)\)：

\[ h(v)=\delta(s,v) \]

之后对每条边重新赋权：

\[ \hat{w}(u,v)=w(u,v)+h(u)-h(v) \]

重新赋权后的边权满足非负性，因此可以对每个源点运行 Dijkstra。

最后再把重新赋权后的最短路径距离还原成原图中的最短路径距离：

\[ d_{uv}=\hat{\delta}(u,v)+h(v)-h(u) \]

Johnson 算法伪代码

JOHNSON(G, w)
1  compute G', where
       G'.V = G.V ∪ {s}
       G'.E = G.E ∪ {(s, v) : v ∈ G.V}
       w(s, v) = 0 for all v ∈ G.V

2  if BELLMAN-FORD(G', w, s) == FALSE
3      print "the input graph contains a negative-weight cycle"

4  else for each vertex v ∈ G'.V
5      set h(v) to the value of δ(s, v) computed by Bellman-Ford

6  for each edge (u, v) ∈ G'.E
7      w_hat(u, v) = w(u, v) + h(u) - h(v)

8  let D = (d_uv) be a new n × n matrix

9  for each vertex u ∈ G.V
10     run DIJKSTRA(G, w_hat, u) to compute δ_hat(u, v) for all v ∈ G.V

11     for each vertex v ∈ G.V
12         d_uv = δ_hat(u, v) + h(v) - h(u)

13 return D

为什么要重新赋权

重新赋权的目的不是改变最短路径结构，而是把边权变成非负，从而可以使用 Dijkstra。

对于任意一条边 \((u,v)\)，由三角不等式可知：

\[ h(v) \le h(u)+w(u,v) \]

移项得：

\[ w(u,v)+h(u)-h(v) \ge 0 \]

也就是：

\[ \hat{w}(u,v) \ge 0 \]

因此，重新赋权之后可以运行 Dijkstra。

image-20260627155550165

image-20260627155558727

距离还原

重新赋权会改变路径权重的数值，但不会改变最短路径的相对关系。

若路径 \(p\) 从 \(u\) 到 \(v\)，则重新赋权后的路径权重为：

\[ \hat{w}(p)=w(p)+h(u)-h(v) \]

因此，重新赋权后的最短距离 \(\hat{\delta}(u,v)\) 与原图最短距离 \(\delta(u,v)\) 的关系为：

\[ \delta(u,v)=\hat{\delta}(u,v)+h(v)-h(u) \]

复杂度

Johnson 算法的大致步骤：

1. 增加新源点并连边。
2. 运行一次 Bellman-Ford。\(O(VE)\)
3. 对所有边重新赋权。
4. 对每个顶点运行一次 Dijkstra。\((V(VlgV+E))\)
5. 还原 \(O(V^2)\) ?

若使用二叉堆实现 Dijkstra，整体复杂度通常写作：

\[ O(VE + V E \lg V) \]

若使用斐波那契堆实现 Dijkstra，整体复杂度通常写作：

\[ O(VE + V^2 \lg V) \]

对于稀疏图，Johnson 算法通常比 Floyd-Warshall 的 \(O(V^3)\) 更有优势，存储空间更小，可以不用算所有点