Johnson’s algorithm on a digraph with negative arcs
This article was prepared in advance of the start of the course. “Algorithms and data structures”
Johnson’s algorithm finds the shortest path between all pairs of vertices in a weighted oriented graph with negative weights without negative contours.
Oh how it sounds! Let’s analyze the condition of the task in parts.
A graph in which each edge has a direction is called oriented (or, briefly, a digraph), and its edges are called arcs. For example, take a digraph of 4 vertices and 8 arcs:
We can move from one vertex to another along arcs in the indicated direction. Moving along one or more arcs is called a “path” or “route”.
For each arc, a number may be indicated that is called the “weight” or “length” of the arc. We will look at each number as a length. The purpose of the algorithm is to find the shortest path between any two vertices. As a warm-up, find the shortest path from peak A to peak D and write the answer in the comments, and we will continue.
You have probably already noticed that some arcs have a negative weight. Traveling along such arcs generates income. The traveler’s dream would be to find a closed path with a negative length and walk along it forever. A closed path is called a “loop” or “contour”, and if there is such a negative contour in the digraph, then there is no solution to the problem, since the minimum path length can tend to minus infinity.
So, we have analyzed all terms of the condition, formulate the purpose of the algorithm again, more consciously:
Johnson’s algorithm finds the shortest path between all pairs of vertices in a weighted oriented graph with negative weights without negative contours.
To solve this problem, you can apply the Floyd-Warshall algorithm, which solves the problem “head-on” by exhaustive search:
for k = 1 to n // n – количество вершин в графе
for x = 1 to n
for y = 1 to n
W[x][y] = min(W[x][y], W[x][k] + W[k][y])W value[x][y] element contains the length of the shortest path from vertex x to vertex y.
The initial values for W are the adjacency matrix of the original graph. Instead of zeros, you need to write plus infinity, since the path between such vertices has not yet been found.
The essence of the algorithm is the constant “relaxation” of the length of the route. At each iteration, we try to get from X to Y through an intermediate vertex K, and if this path is shorter, we remember the reduced length.
The Floyd-Warshall algorithm goes through all possible options for constructing paths, its complexity is just bombic – cubic, and if there are a lot of vertices in the graph, it will work for too long.
There is also an effective Dijkstra algorithm for finding the shortest path from one vertex to all the others. If we apply the Dijkstra algorithm for each vertex, then we will get the shortest paths for all pairs of vertices, and much faster than in the Floyd-Warshell algorithm.
However, Dijkstra’s algorithm does not work correctly with a graph with negative weights.
For example, when searching from vertex A, at the first stage the shortest path to the vertex B (-2) will be found, and at the second stage the “shortest” path will be from B to D (-2 + 6 = 4). On this, the algorithm will start on the result and finish the work. The negative arc of the CD will not even be considered and the correct answer will not be found.
Like this. One algorithm is slow, the other is incorrect.
What to do?
The answer is obvious: use the Johnson algorithm! The idea is brilliant: on the basis of this digraph, form a new digraph so that it does not have negative arcs, and all the shortest paths are the same. Pass the resulting digraph through Dijkstra’s algorithm and get the correct answer at the output!
How do we form such a digraph?
A simple wrong decision is to increase the length of each arc by a constant value so that there are no negative values. Why is this option incorrect? Because it gives odds to shorter routes, unreasonably increasing the total length by the same constant with each new arc.
For example, if in the proposed graph the length of each arc is increased by 4, then the shortest route from A to D will be the direct path: 5 + 1 * 4 = 9. Whereas the correct answer from 3 arcs (ABCD) will receive an extra 12 grams of load and fall out of competition: -2 + 8 – 4 + 3 * 4 = 14.
So, our task is to change the length of each arc in such a way as to get rid of negative arcs and so that all shortest distances remain the same. How to organize this? Let’s add h (X) to the length of each arc XY and subtract h (Y), where h (v) is a “pure” function that defines a certain constant value for each vertex.
We get the lengths of the arcs:
 | |  |
|---|
Let’s see how, in this case, the length of each route changes from vertex A to D:
As you can see, any path from the vertex A to D will change by the same amount, h (A) – h (D), and therefore, all shortest paths will remain the same! Just what you need.
It remains now to find suitable values of the function h so that the modified lengths of the arcs become non-negative.
Consider how you can calculate such values
To do this, add a new source vertex S to the digraph, from which we draw zero arcs to all vertices of the graph. Note that adding a vertex S and arcs S* does not change the shortest paths in the original graph, because all added arcs come only from S, and there is no “zero” route in the opposite direction.
Now run the Bellman-Ford algorithm, which will find the shortest paths from S to all other vertices. This algorithm goes through all arcs N times in a row to “relax” the shortest routes from S to all other vertices. The table lists the “significant” iterations of this algorithm, each column indicates the next arc, which shortens the route to one of the vertices:
The result of this algorithm will give us the desired values of the function h for each vertex. The essence of these values is the shortest path from the vertex S. Since all arcs from S are zero, so the values of the function h are nonpositive. But let this not bother us, the main thing is that the obtained values are fixed, do not change, which means that we can recalculate the lengths of all arcs of the original digraph:
As a result, we get a digraph without negative arcs:
There are no negative arcs, and all the shortest routes are the same as in the original digraph, great! Now we can, with peace of mind, run the Dijkstra algorithm on this digraph for each vertex and get the correct answers.
Let’s see how the shortest routes from peak A to all the others will be found:
In each column, next to the new value of the shortest route, the top is written where we came from. From these letters we can restore the shortest path. For example, the shortest route from A to D is restored from the last column and is written from right to left: A <= B <= C <= D, which was to be found.
So, in this article we looked at the idea of Johnson’s algorithm using a concrete example. Hopefully learning this algorithm on Wikipedia will now become more understandable.
Learn more about the course “Algorithms and data structures”
