Johnson's algorithm: Difference between revisions

Revision as of 03:10, 10 June 2013

Revision as of 04:05, 10 June 2013

Line 1:

{{inline citations|date=June 2013}}

{{For|the scheduling algorithm of the same name|Job Shop Scheduling}}

{{Tree search algorithm}}

'''Johnson's algorithm''' is a way to find the [[shortest path]]s between [[all-pairs shortest path problem|all pairs of vertices]] in a [[sparse graph|sparse]], edge weighted, [[directed graph]]. It allows some of the edge [[weighted graph|weights]] to be [[negative number]]s, but no negative-weight [[cycle (graph theory)|cycles]] may exist. It works by using the [[Bellman–Ford algorithm]] to compute a transformation of the input graph that removes all negative weightςs, allowing [[Dijkstra's algorithm]] to be used on the transformed graph.<ref name="clrs">{{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]] | publisher=MIT Press and McGraw-Hill | isbn=978-0-262-03293-3 | year=2001}}. Section 25.3, "Johnson's algorithm for sparse graphs", pp.&nbsp;636–640.</ref><ref name="black">{{citation | contribution=Johnson's Algorithm | first=Paul E.|last=Black|title=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]| url=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | year=2004 }}.</ref> It is named after [[Donald B. Johnson]], who first published the technique in 1977.<ref>{{citation|first=Donald B.|last=Johnson|authorlink=Donald B. Johnson|title=Efficient algorithms for shortest paths in sparse networks|journal=[[Journal of the ACM]]|volume=24|issue=1|pages=1–13|year=1977|doi=10.1145/321992.321993}}.</ref>

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.<ref>{{citation|first=J. W.|last=Suurballe|title=Disjoint paths in a network|journal=Networks|volume=14|pages=125–145|year=1974|doi=10.1002/net.3230040204|issue=2}}.</ref>

==Algorithm description==

Johnson's algorithm consists of the following steps:<ref name="clrs"/><ref name="black"/>

#First, a new [[Vertex (graph theory)|node]] {{math|''q''}} is added to the graph, connected by zero-weight [[Edge (graph theory)|edges]] to each of the other nodes.

#Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex {{math|''q''}}, to find for each vertex {{math|''v''}} the minimum weight {{math|''h''(''v'')}} of a path from {{math|''q''}} to {{math|''v''}}. If this step detects a negative cycle, the algorithm is terminated.

Line 26 ⟶ 25:

:<math>\bigl(w(s, p1) + h(s) - h(p1)\bigr) + \bigl(w(p1, p2) + h(p1) - h(p2)\bigr) + ... + \bigl(w(p_n, t) + h(p_n) - h(t)\bigr).</math>

Notice that everyEvery <math>+h(p_i)</math> is cancelled by <math>-h(p_i)</math> in the previous bracketed expression; therefore, we are left with the following expression for ''W'':

:<math>\bigl(w(s, p1) + w(p1, p2) + ... + w(p_n, t)\bigr)+ h(s) - h(t)</math>

Notice that theThe 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.<ref name="clrs"/>

==Analysis==

The [[time complexity]] of this algorithm, using [[Fibonacci heap]]s in the implementation of Dijkstra's algorithm, is {{math|O(''V''²log ''V'' + ''VE'')}}: the algorithm uses {{math|O(''VE'')}} time for the Bellman–Ford stage of the algorithm, and {{math|O(''V'' log ''V'' + ''E'')}} for each of {{math|''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 {{math|O(''V''³)}}.<ref name="clrs"/>

==References==

{{reflist}}

*{{citation | contribution=Johnson's Algorithm | first=Paul E.|last=Black|title=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]| url=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | year=2004 }}.

*{{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]] | publisher=MIT Press and McGraw-Hill | isbn=978-0-262-03293-3 | year=2001}}. Section 25.3, "Johnson's algorithm for sparse graphs", pp.&nbsp;636–640.

*{{citation|first=Donald B.|last=Johnson|authorlink=Donald B. Johnson|title=Efficient algorithms for shortest paths in sparse networks|journal=[[Journal of the ACM]]|volume=24|issue=1|pages=1–13|year=1977|doi=10.1145/321992.321993}}.

*{{citation|first=J. W.|last=Suurballe|title=Disjoint paths in a network|journal=Networks|volume=14|pages=125–145|year=1974|doi=10.1002/net.3230040204|issue=2}}.

== External links ==