Johnson's algorithm
Encyclopedia
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in a sparse directed graph
. It allows some of the edge weights to be negative numbers, but no negative-weight cycles
may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm
to be used on the transformed graph. It is named after Donald B. Johnson
, who first published the technique in 1977.
A similar reweighting technique is also used in Suurballe's algorithm
(1974) for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.
The graph on the left of the illustration has two negative edges, but no negative cycles. At the center is shown the new vertex , a shortest path tree as computed by the Bellman–Ford algorithm with as starting vertex, and the values computed at each other node as the length of the shortest path from to that node. Note that these values are all non-positive, because has a length-zero edge to each vertex and the shortest path can be no longer than that edge. On the right is shown the reweighted graph, formed by replacing each edge weight by . In this reweighted graph, all edge weights are non-negative, but the shortest path between any two nodes uses the same sequence of edges as the shortest path between the same two nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph.
Notice that every
is cancelled by 
in the previous bracketed expression; therefore, we are left with the following expression for W:
Notice that the bracketed expression is the weight of p in the original weighting.
Since the reweighting adds the same amount to the weight of every s-t path, a path is a shortest path in the original weighting if and only if it is a shortest path after reweighting. The weight of edges that belong to a shortest path from q to any node is zero, and therefore the lengths of the shortest paths from q to every node become zero in the reweighted graph; however, they still remain shortest paths. Therefore, there can be no negative edges: if edge uv had a negative weight after the reweighting, then the zero-length path from q to u together with this edge would form a negative-length path from q to v, contradicting the fact that all vertices have zero distance from q. The non-existence of negative edges ensures the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.
of this algorithm, using Fibonacci heap
s in the implementation of Dijkstra's algorithm, is : the algorithm uses time for the Bellman–Ford stage of the algorithm, and for each of instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the Floyd–Warshall algorithm, which solves the same problem in time .
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
. It allows some of the edge weights to be negative numbers, but no negative-weight cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
to be used on the transformed graph. It is named after Donald B. Johnson
Donald B. Johnson
Donald Bruce Johnson was an American computer scientist, a researcher in the design and analysis of algorithms, and the founding chair of the computer science department at Dartmouth College....
, who first published the technique in 1977.
A similar reweighting technique is also used in Suurballe's algorithm
Suurballe's algorithm
In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by J. W. Suurballe...
(1974) for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.
Algorithm description
Johnson's algorithm consists of the following steps:- First, a new nodeVertex (graph theory)In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
is added to the graph, connected by zero-weight edges to each of the other nodes. - Second, the Bellman–Ford algorithm is used, starting from the new vertex , to find for each vertex the least weight of a path from to . If this step detects a negative cycle, the algorithm is terminated.
- Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from to , having length , is given the new length .
- Finally, is removed, and Dijkstra's algorithmDijkstra's algorithmDijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
is used to find the shortest paths from each node to every other vertex in the reweighted graph.
Example
The first three stages of Johnson's algorithm are depicted in the illustration below.The graph on the left of the illustration has two negative edges, but no negative cycles. At the center is shown the new vertex , a shortest path tree as computed by the Bellman–Ford algorithm with as starting vertex, and the values computed at each other node as the length of the shortest path from to that node. Note that these values are all non-positive, because has a length-zero edge to each vertex and the shortest path can be no longer than that edge. On the right is shown the reweighted graph, formed by replacing each edge weight by . In this reweighted graph, all edge weights are non-negative, but the shortest path between any two nodes uses the same sequence of edges as the shortest path between the same two nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph.
Correctness
In the reweighted graph, all paths between a pair and of nodes have the same quantity added to them. The previous statement can be proven as follows: Let p be an s-t path. Its weight W in the reweighted graph is given by the following expression:Notice that every
is cancelled by in the previous bracketed expression; therefore, we are left with the following expression for W:Notice that the bracketed expression is the weight of p in the original weighting.
Since the reweighting adds the same amount to the weight of every s-t path, a path is a shortest path in the original weighting if and only if it is a shortest path after reweighting. The weight of edges that belong to a shortest path from q to any node is zero, and therefore the lengths of the shortest paths from q to every node become zero in the reweighted graph; however, they still remain shortest paths. Therefore, there can be no negative edges: if edge uv had a negative weight after the reweighting, then the zero-length path from q to u together with this edge would form a negative-length path from q to v, contradicting the fact that all vertices have zero distance from q. The non-existence of negative edges ensures the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.
Analysis
The time complexityTime complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
of this algorithm, using Fibonacci heap
Fibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
s in the implementation of Dijkstra's algorithm, is : the algorithm uses time for the Bellman–Ford stage of the algorithm, and for each of instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the Floyd–Warshall algorithm, which solves the same problem in time .