约翰逊算法

当需要寻找所有顶点对之间的最短路径时，计算每对顶点间的最短路径看似简单。但在存在负权边的情况下，我们第一反应是为每个顶点调用一次 Bellman-Ford 算法。

这确实能保证检测到有向图中的负权环。然而，这种做法的时间复杂度高达 $O(n^4)$，在最坏情况下如此。

约翰逊算法（Johnson’s algorithm） 对这一思路进行了优化：它通过从每个顶点出发使用单源最短路径算法来解决全对最短路径问题。该算法以唐纳德·B·约翰逊命名，他也因将二叉堆推广为 $d$-叉堆而著称。

核心思想

约翰逊算法的核心思想是：对边的权重进行变换，使得：

1. 新的边权重非负；
2. 在新权重下的最短路径与原权重下的最短路径完全一致。

这种重新加权方式允许我们改用更高效的 Dijkstra 算法，而非每个顶点都运行 Bellman-Ford 算法。当然，我们也必须确保该有向图上的全对最短路径问题是定义良好的。因此，我们首先处理这一点。

引入新顶点的动机

如果图中存在负权环，那将是一个严重问题。
仅从某个任意顶点运行 Bellman-Ford 算法，只能检测出从该顶点可达的负权环。

为了全面检测所有负权环，我们可以构造一个新图 $H$：在原图 $G$ 的基础上新增一个顶点 $s$，并添加从 $s$ 到 $G$ 中所有其他顶点的零权边。注意到，在 $H$ 中不会产生新的环（因为 $s$ 没有入边）。由于 $H$ 中所有顶点均可由 $s$ 到达，只需从 $s$ 运行一次 Bellman-Ford 算法，即可确定 $H$ 中是否存在负权环，从而判断 $G$ 中是否存在负权环。

下图展示了如何从上述有向图构造出 $H$：

在确认不存在负权环的前提下，我们可以继续采用边的重新加权策略。

边的重新加权方案

对于每条边，我们希望通过对它的权重加上某个量来进行变换。之前已证明，简单地给所有边加上一个固定常数是不可行的。

望远镜效应

考虑如下方案：

• 为每个顶点分配一个任意数值；
• 对于每条边 $e$，将其权重增加其起点顶点数值减去终点顶点数值的差值。

考虑一条路径 $\langle v_0, v_1, \cdots, v_k \rangle$，其中每个 $v_i$ 被赋予数值 $a_i$。若采用此重加权方案，则该路径的总权重变化为：

$$\begin{align*} a_0 - &\ \sout{a_1} \\ + &\ \sout{a_1} - \sout{a_2} \\ &\quad\ +\sout{a_2} - \sout{a_3} \\ \ &\quad \quad \qquad \vdots \\ &\qquad \qquad \qquad+ \sout{a_{k-2}} - \sout{a_{k-1}} \\ &\qquad \qquad \qquad \qquad \quad +\ \sout{a_{k-1}} - a_k \\\\ =\quad & a_0 - a_k \\ \end{align*}$$

中间项相互抵消后，路径权重的变化仅取决于路径起点和终点的数值。

由此得出一个惊人结论：任意从顶点 $v_0$ 到 $v_k$ 的路径，其权重均改变相同的量 $a_0 - a_k$。

推论：任意一对顶点之间的最短路径在重新加权后依然保持最短。

尽管最短路径的数值长度增加了 $a_0 - a_k$，但这不是问题——原始长度可通过减去相同量（或等价地，加上 $a_k - a_0$）恢复。

接下来，我们需要选择这些顶点数值 $a_i$，以确保在上述方案下，新边权重均为非负。

保证非负权重

虽然可能存在多种方式为每个顶点 $v_i$ 选择 $a_i$，但既然我们已经在 $H$ 上运行了 Bellman-Ford 算法来检测负权环，我们可以考虑直接使用 $H$ 中各顶点的最短路径长度作为 $a_i$。我们验证一下这种方式是否能保证 $G$ 中的新边权重非负。

设 $e = (v_i, v_{i+1})$ 是 $G$ 中的一条边，权重为 $w_e$。假设在 $H$ 中，从 $s$ 到 $e$ 两端点的最短路径长度分别为：

$$\begin{align*} &a_i \quad = \text{从 } s \text{ 到 } v_i \text{ 的最短路径长度} \\ &a_{i+1} = \text{从 } s \text{ 到 } v_{i+1} \text{ 的最短路径长度} \end{align*}$$

根据三角不等式，显然有：

$$a_{i+1} \leq a_i + w_e$$

移项得：

$$0 \leq (a_i - a_{i+1}) + w_e$$

这个非负数正是我们所提议的新边权重。

因此，使用 $H$ 中从 $s$ 出发的最短路径长度作为顶点数值 $a_i$，恰好满足要求：新边权重非负，且最短路径结构不变。这正是约翰逊算法中选取 $a_i$ 的方法。

约翰逊算法实现

为实现该算法，我们使用一个子程序 AugmentedGraph，输入为有向图 $G$，其功能是创建一个新图 $H$：向 $G$ 添加一个新源点 $s$，并从 $s$ 向 $G$ 中所有顶点添加零权边。该函数返回 $H$ 和源点 $s$。

我们还使用两个二维矩阵来实现约翰逊算法：

• 距离矩阵：
  $d[v][w]$ 存储输入图中从 $v$ 到 $w$ 的最短路径长度。

• 前驱指针矩阵：
  $p[v][w]$ 存储最短 $v-w$ 路径中 $w$ 的前一个顶点。

• 第10–11行：存储 Dijkstra 算法为每个顶点计算出的父节点信息，并存入 $p$ 数组的对应行。
  虽然路径正确，但其长度是基于重加权后的权重。

• 第12行：利用 $w.dist$（即 Dijkstra 找到的 $v-w$ 重加权路径长度），计算出该路径在原始权重下的真实长度。该结果被还原并存入 $d$ 数组中 $v$ 对应的行。

运行时间分析

上述约翰逊算法实现中各语句的运行时间如下：

• 第2行：$O(n+m)$，因为函数需复制图，并添加1个顶点和 $n$ 条边；
• 第3–4行：$O(nm)$；
• 第5–7行：$O(m+n)$，遍历每个顶点的邻接表；
• 第8行：$O(n)$；
• 第9行：$O(n^2\log n + nm\log n)$，Dijkstra 算法每轮耗时 $O(n\log n + m\log n)$；
• 第10–12行：$O(n^2)$，因嵌套在第8行的循环内。

综合各项开销，约翰逊算法的总运行时间为 $O(n^2\log n + nm\log n)$。

若图中边数 $m = O(n)$，则可简化为 $O(n^2\log n)$；否则第二项主导整体复杂度。

一次完整执行演示

1. 输入有向图 $G$；
2. 构造扩展图 $H$，添加源点 $s$ 并连接零权边；
3. 在 $H$ 上运行 Bellman-Ford 算法，计算从 $s$ 到各顶点的最短路径长度；
4. 使用这些最短路径长度对 $G$ 的边进行重新加权；
5. 对 $G$ 中每个顶点依次运行 Dijkstra 算法（基于新权重）；
6. 将 Dijkstra 得到的重加权路径长度还原为原始权重下的真实距离；
7. 最终得到所有顶点对之间的最短路径长度。

最终，我们成功计算出了包含负权边的有向图中所有顶点对之间的最短路径。