Revision as of 09:18, 19 October 2011 edit 130.89.8.165 (talk) changed w(u,p1) to w(s,p1) in the correctness of the algorithm ← Previous edit		Revision as of 15:24, 28 February 2012 edit undo 194.57.41.72 (talk) →Algorithm description Next edit →
Line 9: Johnson's algorithm consists of the following steps: #First, a new [[Vertex (graph theory)\|node]] {{math\|''q''}} is added to the graph, connected by zero-weight [[Edge (graph theory)\|edges]] to each of the other nodes. #Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex {{math\|''q''}}, to find for each vertex {{math\|''v''}} the ~~least~~minimum weight {{math\|''h''(''v'')}} of a path from {{math\|''q''}} to {{math\|''v''}}. If this step detects a negative cycle, the algorithm is terminated. #Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from {{math\|''u''}} to {{math\|''v''}}, having length {{math\|''w(u,v)''}}, is given the new length {{math\|''w(u,v)'' + ''h(u)'' − ''h(v)''}}. #Finally, {{math\|''q''}} is removed, and [[Dijkstra's algorithm]] is used to find the shortest paths from each node {{math\|''s''}} to every other vertex in the reweighted graph.

Johnson's algorithm: Difference between revisions