Johnson's algorithm: Difference between revisions

Revision as of 21:18, 29 November 2009

Revision as of 13:07, 11 December 2009

Line 6:

==Algorithm description==

Johnson's algorithm consists of the following steps:

#First, a new [[Vertex (graph theory)|node]] ''q'' is added to the graph, connected by zero-weight [[Edge (graph theory)|edgeedges]] to each other node.

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