Johnson's full source negative power shortest path algorithm detailed explanation

Floyd-Warshall algorithmThe shortest path of any two points in the graph can be solved, which is suitable for dense graphs, but the time complexity is$O(n³)$；Dijkstra AlgorithmThe time complexity of solving the shortest path of a single source is$O(m + n log n)$, do it once for each node, and the shortest path to the entire source can also be achieved, but this method is only applicable to non-negative weight edge graphs.

The Johnson algorithm is designed to solve this problem, which supports negative power edges (of course, no negative power ring). Combining the advantages of two algorithms, time complexity$O(nm + n² log n)$, significantly better than Floyd-Warshall in sparse graphs, combining the efficiency of Dijkstra with the flexibility of Bellman-Ford.

1 Add a virtual node

operate: In the original image$G$Add a virtual node to$s$and add from$s$To all the edges of the original nodes, the weight is 0.
Purpose: Prepare for subsequent calculation of potential energy functions.

2 Calculate potential energy function$h(v)$

step：
1. useBellman-Ford AlgorithmCalculate from$s$The shortest path to all original nodes, the result is$h(v)$。
2. If a negative weight ring is detected, the algorithm terminates (the original image has no valid shortest path at this time).

3 Adjust edge weight to non-negative value

formula: For each edge in the original image$(u, v)$, adjust the weight to:

\[w'(u, v) = w(u, v) + h(u) - h(v) \]
Key Nature: After this adjustment, all new edge weights will be adjusted$w'(u, v)$All are non-negative. And it meets "the shortest circuit of the original image is also the shortest circuit of the new image"

4 Run the Dijkstra algorithm

operate: For the adjusted graph, for each node$u$Run the Dijkstra algorithm once to get the shortest path$d'(u, v)$。

5 Restore the original shortest path

formula: In the original picture$u$arrive$v$The shortest path is:

\[d(u, v) = d'(u, v) - h(u) + h(v) \]

Why is it right?

1 Non-negativeness of side rights adjustment

$h$is the distance from the virtual point to the node, according to the shortest path nature of Bellman-Ford, for any edge$(u, v)$have:

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

Move the item to:

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

Therefore, the adjusted weight$w'(u, v)$Non-negative, Dijkstra algorithm can run correctly.

2 Equivalence of the shortest path

Let's set a path in the original image$p = v₀ → v₁ → ... → vₖ$The sum of weights is:

\[W(p) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \]

The adjusted weight sum is:

\[W'(p) = \sum_{i=0}^{k-1} [w(v_i, v_{i+1}) + h(v_i) - h(v_{i+1})] = W(p) + h(v₀) - h(v_k) \]

On the path$h$offset, because$h(v₀) - h(v_k)$It is a constant. All paths at the two corresponding points on the original image and the new image are only different from the constant. Then the shortest path of the original image is still the shortest path of the new image.

Time complexity analysis

step	Time complexity
Bellman-Ford	$O(nm)$
n times Dijkstra	$O(n(m + n log n))$
Total time	$O(nm + n² log n) $

Applicable scenarios: When the sparse picture is, the time is close$O(n² log n)$, far better than Floyd-Warshall's$O(n³)$. The gap on the dense chart narrows.