Johnson's algorithm: Difference between revisions

Revision as of 14:40, 29 August 2005

Revision as of 04:31, 20 November 2005

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 [[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'').

Line 7:

==References==

* Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. ''[[Journal of the ACM]]'' 24(1):1–13, January 1977. {{doi|10.1145/321992.321993}}

*{{Web reference | title=Johnson's Algorithm | work=AUTHOR(S), "Johnson's algorithm", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST. | URL=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | date=14 June | year=2005 }}