Johnson's algorithm: Difference between revisions

Revision as of 00:15, 17 February 2008

Revision as of 21:57, 4 April 2008

Line 1:

{{Tree search algorithm}}

'''Johnson's algorithm''' is a way to solve the [[all-pairs shortest path problem]] in a [[sparse matrix|sparse]], [[weighted graph|weighted]], [[directed graph]]. in which some of the edge weights may be [[negative number]]s, but no negative-weight [[cycle (graph theory)|cycles]] exist.

It consists of the following steps:

First, it adds a new [[Vertex (graph theory)|node]] with zero weight [[Edge (graph theory)|edge]] from it to all other nodes, and runs the [[Bellman-Ford algorithm]] to check for negative weight cycles and find ''h''(''v''), the least weight of a path from the new node to node ''v''. Next it reweights the edges using the nodes' ''h''(''v'') values. Finally for each node, it runs [[Dijkstra's algorithm]] and stores the computed least weight to other nodes, reweighted using the nodes' ''h''(''v'') values, as the final weight. The [[time complexity]] is O(''V''²log ''V'' + ''VE'').

#First, it adds a new [[Vertex (graph theory)|node]] ''q'' to the graph, with a zero weight [[Edge (graph theory)|edge]] connecting ''q'' to each other node.

#Second, it runs the [[Bellman-Ford algorithm]], starting from the new vertex ''q'', to check for negative weight cycles and to find ''h''(''v''), the least weight of a path from ''q'' to ''v''.

#Next it reweights the edges of the original graph 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'', it runs [[Dijkstra's algorithm]] to find the shortest paths from ''s'' to each other vertex in the graph, using these modified weights to measure the length of each path.

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. 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.

==See also==

* [[Floyd-Warshall algorithm]]

The [[time complexity]] of this algorithm, using [[Fibonacci heap]]s in the implementation of Dijkstra's algorithm, is O(''V''²log ''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''³).

==References==

* Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. ''[[Journal of the ACM]]'' 24(1):1–13, January 1977. {{doi|10.1145/321992.321993}}

*{{cite web | title=Johnson's Algorithm | work=AUTHOR(S)Paul E. Black, "Johnson's algorithm", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST. | url=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | accessdaymonth=14 June | accessyear=2005 }}

*{{Citation | last1=Cormen | first1=Thomas H. | author1-link=Thomas H. Cormen | last2=Leiserson | first2=Charles E. | author2-link=Charles E. Leiserson | last3=Rivest | first3=Ronald L. | author3-link=Ronald L. Rivest | last4=Stein | first4=Clifford | author4-link=Clifford Stein | title=[[Introduction to Algorithms|Introduction to Algorithms]] | publisher=MIT Press and McGraw-Hill | isbn=978-0-262-03293-3 | year=2001}}. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.

[[Category:Graph algorithms]]