Johnson算法可以在 O(V^2lgE + VE)的时间找到所有结点之间的最短路径。对于稀疏图，Johnson算法的渐进表现要优于 Floyd-Warshall 算法。Johnson算法在运行中需要使用 Dijkstra算法和 Bellman-Ford算法作为子程序。

所有结点对最短路径，我们可以运行 |V| 次单源最短路径算法，每次使用不同的的结点作为源点。如果跑 |V|次Bellman-Ford算法，时间复杂度是 O(V^2E)。如果图中没有负权重的边，我们也可以跑 |V|次 Dijkstra算法，那么时间复杂度是O(VElogV) (Dijkstra有堆优化）。这样在稀疏图上相较于Floyd算法 O(V^3)仍然更优秀。

所以我们可以对原图进行预处理，取保所有边都为非负，然后跑|V|次Dijkstra来解决这个问题。

那么该如何保证所有边的权重都为非负呢？

Johnson算法通过重新赋予权重的技术来实现，具体做法如下：

其中前两部和差分系统算法是一样的，后面两步很简单，大致流程如下图所示：

其中第一步，新增虚拟结点 v_0 (前两幅图中的黑色结点），并且到其他的结点都记为 0；然后调用 Bellman-Ford算法，计算 v_0到其他结点的最短路径权重，然后对每条边从新赋予权重：w'(u,v) = w(u,v) + h(u)-h(v)。最后在对每个运行 Dijkstra算法，得到最终结果。

重新赋值权重可以用来维持最短路径，可以使用下面的的引理得到。这里我们使用 \delta 表示 w 所导出的最短路径权重，\delta' 来表示 w' 所导出的最短路径权重。

证明：

我们先证明：w'(p) = w(p) + h(v_0)-h(v_k)。

\begin{equation} \begin{split} w'(p) &= \sum_{i=1}^k w'(v_{i-1},v_i) \\ &= \sum_{i=1}^k （w(v_{i-1},v_i) + h(v_{i-1}) - h(v_i) \\ &= \sum_{i=1}^k w(v_{i-1},v_i) + h(v_0) - h(v_k) \\ &= w(p) + h(v_0) - h(v_k) \end{split} \end{equation}\\

因此，对于结点 v_0 到 v_k 的任意路径 p，我们有 w'(p) = w(p) + h(v_0)-h(v_k)。因为 h(v_0) 和 h(v_k)不依赖任何具体的路径，如果从结点 v_0 到 v_k 的一条路径在使用权重函数 w 时比另一条路径短，则其在使用权重函数 w' 时也比另一条短。因此， w(p) = \delta(v_0,v_k)当且仅当 w'(p)=\delta'(v_0,v_k)。

最后，证明 G在使用权重函数 w 时包含一个权重为负的环路当且仅当 p 在使用权重函数 w'也包含一个权重为负的环路。考虑任意环路 c=\lt v_0, v_1, ...,v_k\gt，其中 v_0 = v_k 。因为前面证明，可以得出 w'(c) = w(c) + h(v_0)-h(v_k) = w(c)。因此，环路 c 在使用权重函数 w 时为负值当且仅当在使用 w' 时也会负值。

通过上面的引理我们可以知道。对与所有结点对 u,v \in V ，一条路径 p 是在使用权重函数 w 时从结点 u 到 v 的一条最短路径，当且仅当 p 是在使用权重函数 w' 时从 u 到 v 的一条最短路径。也就是说，我们可以使用新的权重函数 w' ，而且不会影响到图各结点间最短路径。所以我们完全可以找到这样一个新的权重函数 w' ，对所有边 (u,v) \in E,\; w'(u,v) 都是非负的权重函数。这样我们接可以使用Dijkstra算法来计算每个结点的最短路径权重了。

下面我们证明根据Johnson算法的策略，其新的权值函数满足 (u,v) \in E, \; w'(u,v) \geqslant 0。

根据Johnson算法的策略：

新得到的图为 G'=(V',E') ，其中

V' = V \cup \{s\}; \; E' = E \cup \{(s,v): v \in V \}; \; w(s,v)= 0 \\

当算法第二步执行完Bellman-Ford算法后，对于所有结点 v \in V' 有 h(v) = \delta(s,v)。根据Bellman-Ford算法的性质，松弛操作之后，对于所有边 (u,v) \in E'，有 h(v) \leqslant h(u) + w(u,v)。因此，如果我们根据前面引理 w'(u,v) = w(u,v) + h(u)-h(v) 来定义新的权重函数 w'，则有 w'(u,v) = w(u,v) + h(u) - h(v) \geqslant 0，得证。