Johnson's algorithm: Difference between revisions

Revision as of 06:17, 16 December 2004

Revision as of 08:28, 16 December 2004

Line 1:

An'''Johnson's algorithm''' is a way to solve the all pairs [[shortest path problem]] in a [[sparse]] [[weighted]], [[directed graph]].

First, it adds a new [[node]] with zero weight [[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² log V + VE).

:O(''V''²log ''V'' + ''VE'').

[[Category:Graph algorithms]]