Content deleted Content added
The link to a german version of "Johnsons algorithm" is semantically not the same algorithm. That is the association: http://de.wikipedia.org/w/index.php?title=Johnson-Algorithmus_(Graphentheorie) |
brief summary of the algorithm in the lede |
||
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.
==Algorithm description==
| |||