Johnson's algorithm: Difference between revisions

Revision as of 11:33, 3 August 2007

Revision as of 00:00, 22 September 2007

Line 3:

'''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 [[Vertex (graph theory)|node]] with zero weight [[Edge (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''²²log ''V'' + ''VE'').

==See also==

Line 17:

[[de:Johnson-Algorithmus]]

[[it:Regola di Johnson]]

[[he:האלגוריתם של ג'ונסון]]

[[pl:Algorytm Johnsona]]

[[it:Regola di Johnson]]