Editing Johnson's algorithm (section)

{{Short description|Computer-based path-finding method}}
{{For|the scheduling 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 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.&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>