Content deleted Content added
m Reverted edits by 217.134.84.6 (talk) to last version by Ligulembot |
m Robot-assisted disambiguation (you can help!): Edge |
||
Line 1:
'''Johnson's algorithm''' is a way to solve the [[all-pairs shortest path problem]] in a [[sparse matrix|sparse]], [[weighted graph|weighted]], [[directed graph]].
First, it adds a new [[node]] with zero weight [[graph theory|edge]] from it to all other nodes, and runs the [[Bellman-Ford algorithm]] to check for negative weight cycles and find ''h''(''v''), the least weight of a path from the new node to node ''v''. Next it reweights the edges using the nodes' ''h''(''v'') values. Finally for each node, it runs [[Dijkstra's algorithm]] and stores the computed least weight to other nodes, reweighted using the nodes' ''h''(''v'') values, as the final weight. The [[time complexity]] is O(''V''<sup>2</sup>log ''V'' + ''VE'').
==See also==
| |||