Johnson's Algorithm
   HOME

TheInfoList



OR:

Johnson's algorithm is a way to find the
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...
s between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be
negative number In mathematics, a negative number is the opposite (mathematics), opposite of a positive real number. Equivalently, a negative number is a real number that is inequality (mathematics), less than 0, zero. Negative numbers are often used to represe ...
s, but no negative-weight
cycles Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...
may exist. It works by using the
Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex (graph theory), vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more ...
to compute a transformation of the input graph that removes all negative weights, allowing
Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
to be used on the transformed graph.. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in a version of the successive shortest paths algorithm for the minimum cost flow problem due to Edmonds and Karp, as well as in
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 vertex (graph theory), vertices and ha ...
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
node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines ...
is added to the graph, connected by zero-weight edges to each of the other nodes. #Second, the
Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex (graph theory), vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more ...
is used, starting from the new vertex , to find for each vertex the minimum 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 algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
is used to find the shortest paths from each node to every other vertex in the reweighted graph. The distance in the original graph is then computed for each distance (, ), by adding to the distance returned by Dijkstra's algorithm.


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. The center graph shows 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 be an path. Its weight W in the reweighted graph is given by the following expression: \left(w(s, p_1) + h(s) - h(p_1)\right) + \left(w(p_1, p_2) + h(p_1) - h(p_2)\right) + ... + \left(w(p_n, t) + h(p_n) - h(t)\right). Every +h(p_i) is cancelled by -h(p_i) in the previous bracketed expression; therefore, we are left with the following expression for ''W'': \left(w(s, p_1) + w(p_1, p_2) + \cdots + w(p_n, t)\right)+ h(s) - h(t) The bracketed expression is the weight of ''p'' in the original weighting. Since the reweighting adds the same amount to the weight of every 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 complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
of this algorithm, using
Fibonacci heap In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binar ...
s in the implementation of Dijkstra's algorithm, is O(, V, ^2\log , V, + , V, , E, ): the algorithm uses O(, V, , E, ) time for the Bellman–Ford stage of the algorithm, and O(, V, \log , V, + , E, ) for each of the , V, instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the
Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with po ...
, which solves the same problem in time O(, V, ^3).


References


External links


Boost: All Pairs Shortest Paths
{{Graph traversal algorithms Graph algorithms Search algorithms Graph distance