Johnson's algorithm

In every company, the most essential task is managing the movement of money in and out in terms of income and expenditure, also known as cash flow. Such data is usually collected in tables and passed to the finance department. Afterward, the information is represented in a weighted graph where nodes stand for the economic activities performed by the company as shown below:

Negative weights indicate that the company earns money from the activity. The goal is to minimize the cost of every chain of activities. In other words, it is required to find the shortest paths between all pairs of nodes. The bigger the company, the larger the data graph. Johnson's algorithm is able to solve this task successfully in a reasonable amount of time.

Description of the algorithm

We are already familiar with a couple of algorithms that solve the SSSP problem. The fast way would be to apply Dijkstra's algorithm for every node and solve our all-pairs shortest path problem. However, as we know, we would have trouble with negative edges. Naturally, we might want to repeatedly apply the Bellman-Ford algorithm instead, but this is relatively slow.

We don't have all day, our aim is to be efficient. The main idea of Johnson's approach is to use both algorithms mentioned above as subroutines: we remove all the negative weights using Bellman-Ford, which allows Dijkstra's algorithm to work correctly. In more detail, the steps of Johnson's algorithm can be described as follows:

1. Add a new node $q$ to the given graph $G = (V, E)$. Connect $q$ to all other nodes using edges of weight $w_{q,v} = 0.$
2. Apply the Bellman-Ford algorithm to the new graph choosing $q$ as the source node. For each node $v$, let $d_v$ denote the weight of the shortest path from $q$ to $v$. If negative cycles are detected, notify about it and terminate.
3. Reweight the edges of the initial graph $G$ eliminating negative edges. This can be accomplished by assigning a new nonnegative weight, namely $w_{u,v} + d_u - d_v$, to every edge $(u, v)$ of weight $w_{u,v}$.
4. Remove $q$. Apply Dijkstra's algorithm $|V|$ times, each time choosing a new starting node, in order to find the weights of the shortest paths $D_{u,v}$ between all pairs of nodes in the reweighted graph $G'.$
5. The original weights of the shortest paths can be obtained by adding $d_v - d_u$ to each distance $D_{u, v}$ computed during the previous step.

If you are an attentive reader, you must be asking yourself several questions now. Why are the new weights $w_{u,v} + d_u - d_v$ guaranteed to be nonnegative? What about the fifth step, isn't it an abstract assumption? The next paragraph is dedicated solely to these two questions.

Correctness of the algorithm

The correctness of Johnson's algorithm is mainly implied by the correctness of its subroutines. However, as we mentioned above, we have made two nontrivial statements:

• All edges in the reweighted graph have nonnegative weights.
• The shortest paths computed by Dijkstra's algorithm in $G'$ remain shortest paths in the original graph $G$.

First, let's notice that in $G'$, the weight of every path between two nodes, say $s$ and $t$, differs from the original weight by $d_s - d_t$. Indeed, consider the path $s \to v_1 \to \dots \to v_n \to t$. Its weight is equal to

$w_{s,v_1} + d_s - d_{v_1} + w_{v_1, v_2} + d_{v_1} - d_{v_2} + \dots + w_{v_n, t} + d_{v_n} - d_t = (w_{s,v_1} + \dots w_{v_n, t}) + d_s - d_t$

as each $d_{v_i}$ is canceled. Therefore, every shortest path in the reweighted graph remains shortest in the original one and their weight can be calculated as we assumed in step $5$. Still, we need to prove the first assumption that all the conditions to apply Dijkstra's algorithm have been met.

What if some edge $(u,v)$ has a negative weight $w'_{u,v}$ after reweighting? Consider the shortest path from $q$ to $u$. Based on what we proved above, its weight becomes $d'_u = d_u + d_q - d_u = d_q = 0$ after the reweighting process. Analogously, $d'_v = 0.$ Besides, they still remain shortest paths. However, with $w'_{u,v}$ being negative, we obtain a shorter path from $q$ to $v$, namely, the blue path from $q$ to $u$ together with the red edge $(u,v)$, which contradicts the fact that the shortest path from $q$ to $v$ costs $d'_v = 0.$

An example

Let's get down to business. Literally. Our company expects us to compute the all-pairs shortest paths in the cash flow graph. It is a perfect chance to apply Johnson's algorithm.

1. Add a new node, say $0$, and connect it to nodes $1, 2, 3, 4$, and $5$ using zero-weight edges as shown in picture 1.
2. We already know how the Bellman-Ford algorithm works, hence we are going to immediately write the final weights of the shortest paths choosing node $0$ as the source.

   

3. With these values calculated, we can easily reweight every edge of the initial graph. For example, the edge $(2,3)$ will cost $w_{2,3} + d_2 - d_3 = 5 + (-4) - 0 = 1.$ After step $3$, the reweighted graph will look like the one in picture 3.

   

4. Remove the extra edge $0.$ We end up with the graph in picture 4.0. Now we need to apply Dijkstra's algorithm $5$ times: first choosing $1$ as the starting node, then the source will be $2$, and so on until we find all shortest paths between each pair of nodes. For obvious reasons, we are not going to describe how Dijkstra's algorithm works in detail. We shall simply display the final values for every instantiation of it in the pictures below.

   

5. Now we need to reverse the reweighting process by adding the value $d_v - d_u$ to every shortest path weight $D_{u,v}$. For instance, the cost of the shortest path from node $2$ to node $1$ becomes $D_{2,1} + d_1 - d_2 = 1 + (-2) - (-4) = 3.$ The final values are represented in table 5.

   

Based on the results above, the company is going to make decisions about the activities worth performing and the order of their completion, picking the ones that are more profitable. For example, doing the second activity in the beginning and the fourth one in the end is quite expensive; meanwhile, performing activity $4$ and then the second one is extremely beneficial for the company.

Time complexity

For a graph with $|V| = n$ nodes and $|E| = m$ edges, the time complexity of Johnson's algorithm is $O(n^2\log n + nm)$. Let's analyze every phase in more detail. Bellman-Ford takes $O(nm)$. On the other hand, one can implement Dijkstra's algorithm in $O(n\log n + m)$ using a Fibonacci heap. We apply $n$ instantiations; therefore, step $4$ uses $O(n^2\log n + nm)$ time. The first, third, and fifth steps can be implemented practically at no extra cost. Overall, Johnson's algorithm takes $O(n^2\log n + nm)$ time.

Conclusion

Let's sum up what we have learned in this topic. Johnson's algorithm is a relatively fast algorithm for solving the all-pairs shortest path problem, and it is able to handle negative cycles as well. It can be easily implemented following these five steps:

1. Add a new node. Connect it to every other node using zero-weight edges.
2. Calculate the shortest paths from this node to each node using the Bellman-Ford algorithm.
3. Reweight the graph so that no negative edges are left.
4. Apply Dijkstra's algorithm $|V|$ times to find the shortest paths between each pair of nodes.
5. Using the values found in step 4, calculate the weights of all shortest paths in the original graph.

In the case of sparse graphs, Johnson's algorithm works remarkably faster than many other all-pairs algorithms, as its time complexity depends on the number of edges.