Content deleted Content added
Added reference to Edmonds and Karp (see discussion at the end of page 256 of the cited paper) |
Grapesurgeon (talk | contribs) not necessarily strictly computer based, and not just pathfinding but shortest paths |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|
{{For|the scheduling algorithm of the same name|Job shop scheduling}}▼
{{Infobox Algorithm
|class=[[All-pairs shortest path problem]] (for weighted graphs)
Line 8 ⟶ 9:
|space=
}}
▲{{For|the scheduling algorithm of the same name|Job shop scheduling}}
'''Johnson's algorithm''' is a way to find the [[shortest path]]s between [[all-pairs shortest path problem|all pairs of vertices]] in an [[weighted graph|edge-weighted]] [[directed graph]]. It allows some of the edge 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 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. 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=
==Algorithm description==
Line 19 ⟶ 18:
#First, a new [[Vertex (graph theory)|node]] {{mvar|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 {{mvar|q}}, to find for each vertex {{mvar|v}} the minimum weight {{math|''h''(''v'')}} of a path from {{mvar|q}} to {{mvar|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 {{mvar|u}} to {{mvar|v}}, having length {{tmath|w(u, v)}}, is given the new length {{math|''w''(''u'',''v'') + ''h''(''u'') − ''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}}
==Example==
Line 27 ⟶ 26:
[[File:Johnson's algorithm.svg|540px|center]]
The graph on the left of the illustration has two negative edges, but no negative cycles. The center graph shows the new vertex {{mvar|q}}, a shortest path tree as computed by the Bellman–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'') + ''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.
==Correctness==
| |||