Johnson's algorithm

Johnson's algorithm

Johnson's algorithm is a way to find 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.

Algorithm description

Johnson's algorithm consists of the following steps:
#First, a new node "q" is added to the graph, connected by zero-weight edge to each other node.
#Second, the Bellman-Ford algorithm is used, starting from the new vertex "q", to find for each vertex "v" the least weight "h"("v") of a path from "q" to "v". 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 "u" to "v", having length "w(u,v)", is given the new length "w(u,v)" + "h(u)" −"h(v)".
#Finally, for each node "s", Dijkstra's algorithm is used to find the shortest paths from "s" to each other vertex in the reweighted graph.

In the reweighted graph, all paths between a pair "s" and "t" of nodes have the same quantity "h(s)" -"h(t)" added to them, so a path that is shortest in the original graph remains shortest in the modified graph and vice versa. However, due to the way the values "h(v)" were computed, all modified edge lengths are non-negative, ensuring 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 of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is O("V"2log "V" + "VE"): the algorithm uses O("VE") time for the Bellman-Ford stage of the algorithm, and O("V" log "V" + "E") for each of "V" 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 O("V"3).

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 "q", a shortest path tree as computed by the Bellman-Ford algorithm with "q" as starting vertex, and the values "h"("v") computed at each other node as the length of the shortest path from "q" to that node. Note that these values are all non-positive, because "q" 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 "w(u,v)" by "w(u,v)" + "h(u)" −"h(v)". 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.

References

*. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Steinhaus-Johnson-Trotter algorithm — The Steinhaus Johnson Trotter algorithm or Johnson Trotter algorithm is an algorithm which generates permutations by transposing elements.AlgorithmThe algorithm is setup with the idea that only one set of neighbors needs to swap positions and… …   Wikipedia

  • Rader's FFT algorithm — Rader s algorithm (1968) is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re expressing the DFT as a cyclic convolution. (The other algorithm for FFTs of prime sizes, Bluestein s… …   Wikipedia

  • Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Prim's algorithm — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Donald B. Johnson — Donald Bruce Johnson (died 1994)[1][2] 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.[3] Johnson received his Ph.D. from… …   Wikipedia

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… …   Wikipedia

  • Texas Medication Algorithm Project — The Texas Medication Algorithm Project (TMAP) [ [http://www.dshs.state.tx.us/mhprograms/TMAPtoc.shtm DSHS.state.tx.us] Texas Medication Algorithm Project (official site with algorithms etc), Texas Department of State Health Services] is a… …   Wikipedia

  • Gilbert–Johnson–Keerthi distance algorithm — The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets. Unlike many other distance algorithms, it does not require that the geometry data be stored in any specific format, but… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”