Johnson's algorithm: Difference between revisions

Revision as of 15:05, 11 April 2009

Revision as of 21:02, 11 April 2009

Line 18:

The first three stages of Johnson's algorithm are depicted in the illustration below.

[[ImageFile:Johnson's algorithm.svg|540px|center]]

The graph on the left of the illustration has two negative edges, but no negative cycles. At the center is shown the new vertex ''q'', a shortest path tree as computed by the Bellman-Ford algorithm with ''q'' as starting vertex, and the values ''h''(''v'') computed at each other node as the length of the shortest path from ''q'' to that node. Note that these values are all non-positive, because ''q'' has a length-zero edge to each vertex and the shortest path can be no longer than that edge. On the right is shown the reweighted graph, formed by replacing each edge weight ''w(u,v)'' by ''w(u,v)'' + ''h(u)'' −''h(v)''. In this reweighted graph, all edge weights are non-negative, but the shortest path between any two nodes uses the same sequence of edges as the shortest path between the same two nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph.

Line 27:

*{{citation | contribution=Johnson's Algorithm | first=Paul E.|last=Black|title=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]| url=http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html | year=2004 }}.

*{{Citation | last1=Cormen | first1=Thomas H. | author1-link=Thomas H. Cormen | last2=Leiserson | first2=Charles E. | author2-link=Charles E. Leiserson | last3=Rivest | first3=Ronald L. | author3-link=Ronald L. Rivest | last4=Stein | first4=Clifford | author4-link=Clifford Stein | title=[[Introduction to Algorithms|Introduction to Algorithms]] | publisher=MIT Press and McGraw-Hill | isbn=978-0-262-03293-3 | year=2001}}. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.

[[Category:Graph algorithms]]