Johnson's algorithm: Difference between revisions

Revision as of 02:59, 1 November 2009

Latest revision as of 13:41, 22 June 2025

(74 intermediate revisions by 53 users not shown)

Line 1:

{{Short description|Method to find shortest paths}}

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

{{TreeFor|the searchscheduling algorithm of the same name|Job shop scheduling}}

{{Infobox Algorithm

|class=[[All-pairs shortest path problem]] (for weighted graphs)

|image=

|caption =

|data=[[Graph (data structure)|Graph]]

|time=<math>O (|V|^2 \log |V| + |V||E|)</math>

|space=

}}

'''Johnson's algorithm''' is a way to find the [[shortest path]]s between [[all-pairs shortest path problem|all pairs of vertices]] in aan [[sparseweighted graph|sparseedge-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-FordBellman–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.<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=Ron 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=https://xlinux.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|s2cid=207678246|doi-access=free}}.</ref>

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,<ref>{{citation|first1=J.|last1=Edmonds|first2=Richard M.|last2=Karp|title=Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems|journal=[[Journal of the ACM]]|volume=19|issue=2|pages=248–264|year=1972|doi=10.1145/321694.321699}}.</ref> as well as in [[Suurballe's algorithm]] 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:

#First, a new [[Vertex (graph theory)|node]] ''q'' is added to the graph, connected by zero-weight [[Edge (graph theory)|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)''&nbsp;+&nbsp;''h(u)''&nbsp;&minus;''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.

==Algorithm description==

In the reweighted graph, all paths between a pair ''s'' and ''t'' of nodes have the same quantity ''h(s)''&nbsp;-''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.

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

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

==Analysis==

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

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''³).

#Next the edges of the original graph are reweighted using the values computed by the Bellman-FordBellman–Ford algorithm: an edge from ''{{mvar|u''}} to ''{{mvar|v''}}, having length ''{{tmath|w(u, v)''}}, is given the new length {{math|''w''(''u'',''v)''&nbsp;) +&nbsp; ''h''(''u)''&nbsp;) &minus; ''h''(''v)'')}}.

#Finally, {{mvar|q}} is removed, and [[Dijkstra's algorithm]] is used to find the shortest paths from each node {{mvar|s}} to every other vertex in the reweighted graph. The distance in the original graph is then computed for each distance {{mvar|D}}({{mvar|u}}, {{mvar|v}}), by adding {{mvar|''h''(''v'') &minus; ''h''(''u'')}} to the distance returned by Dijkstra's algorithm.

==Example==

Line 21 ⟶ 26:

[[File:Johnson's algorithm.svg|540px|center]]

The graph on the left of the illustration has two negative edges, but no negative cycles. At theThe center isgraph shownshows the new vertex ''{{mvar|q''}}, a shortest path tree as computed by the Bellman-FordBellman–Ford algorithm with ''{{mvar|q''}} as starting vertex, and the values {{math|''h''(''v'')}} computed at each other node as the length of the shortest path from ''{{mvar|q''}} to that node. Note that these values are all non-positive, because ''{{mvar|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 ''{{tmath|w(u, v)''}} by {{math|''w''(''u'',''v)''&nbsp;) +&nbsp; ''h''(''u)''&nbsp;) &minus; ''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==

==Correctness==

*{{citation|first=Donald B.|last=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}}.

In the reweighted graph, all paths between a pair {{mvar|s}} and {{mvar|t}} of nodes have the same quantity {{math|''h''(''s'') &minus; ''h''(''t'')}} added to them. The previous statement can be proven as follows: Let {{mvar|p}} be an {{tmath|s-t}} path. Its weight W in the reweighted graph is given by the following expression:

<math display="block">\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).</math>

*{{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 }}.

Every <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'':

*{{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. 636–640.

<math display="block">\left(w(s, p_1) + w(p_1, p_2) + \cdots + w(p_n, t)\right)+ h(s) - h(t)</math>

[[Category:Graph algorithms]]

The bracketed expression is the weight of ''p'' in the original weighting.

[[es:Algoritmo de Johnson]]

[[fa:الگوریتم جانسون]]

[[he:האלגוריתם של ג'ונסון]]

[[pl:Algorytm Johnsona]]

[[ru:Алгоритм Джонсона]]

Since the reweighting adds the same amount to the weight of every {{tmath|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"/>

== External Links ==

==Analysis==

[http://www.itl.nist.gov/div897/sqg/dads/HTML/johnsonsAlgorithm.html NIST: Johnson's Algorithm]

The [[time complexity]] of this algorithm, using [[Fibonacci heap]]s in the implementation of Dijkstra's algorithm, is <math>O(''|V''^{|^2}\log ''|V''| + ''VE''|V||E|)</math>: the algorithm uses <math>O(''VE''|V||E|)</math> time for the Bellman-FordBellman–Ford stage of the algorithm, and <math>O(''|V'' |\log ''|V''| + ''|E''|)</math> for each of ''the <math>|V''|</math> instantiations of Dijkstra's algorithm. Thus, when the graph is [[sparse graph|sparse]], the total time can be faster than the [[Floyd-WarshallFloyd–Warshall algorithm]], which solves the same problem in time <math>O(''|V''<sup>|^3)</supmath>).<ref name="clrs"/>

==References==

[http://wiki.syncleus.com/index.php/DANN Open Source Java AI Library with Implementation] ([http://bugs.syncleus.com/trac.cgi/dANN/browser/trunk/projects/java_dann/src/com/syncleus/dann/graph/search/pathfinding/JohnsonGraphTransformer.java source])

{{reflist}}

== External Linkslinks ==

*[http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/johnson_all_pairs_shortest.html Boost: All Pairs Shortest Paths]

{{Graph traversal algorithms}}

[[Category:Graph algorithms]]

[[Category:Search algorithms]]

[[Category:Graph distance]]