Johnson's algorithm: Difference between revisions

Revision as of 15:12, 13 April 2010

Revision as of 06:38, 21 April 2010

Line 9:

#Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex ''q'', to find for each vertex ''v'' the least weight ''h''(''v'') of a path from ''q'' to ''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 ''u'' to ''v'', having length ''w(u,v)'', is given the new length ''w(u,v)'' + ''h(u)'' −''h(v)''.

#Finally, for each node ''sq'' is removed, and [[Dijkstra's algorithm]] is used to find the shortest paths from each node ''s'' to eachevery other vertex in the reweighted graph.

In the reweighted graph, all paths between a pair ''s'' and ''t'' of nodes have the same quantity ''h(s)'' −''h(t)'' added to them, so a path that is shortest in the original graph remains shortest in the modified graph and vice versa. However, due to the way the values ''h(v)'' were computed, all modified edge lengths are non-negative, ensuring the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.