Content deleted Content added
brief summary of the algorithm in the lede |
eponym |
||
Line 1:
{{Tree search algorithm}}
'''Johnson's algorithm''' is a way to find [[shortest path]]s between [[all-pairs shortest path problem|all pairs of vertices]] in a [[sparse graph|sparse]] [[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 weights, allowing [[Dijkstra's algorithm]] to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.
==Algorithm description==
| |||