Johnson's algorithm: Difference between revisions

Revision as of 21:57, 4 April 2008

Revision as of 22:03, 4 April 2008

Line 5:

It consists of the following steps:

#First, it adds a new [[Vertex (graph theory)|node]] ''q'' to the graph, with a zero weight [[Edge (graph theory)|edge]] connecting ''q'' to each other node.

#Second, it runs the [[Bellman-Ford algorithm]], starting from the new vertex ''q'', to check for negative weight cycles and to find for each vertex ''v'' the least weight ''h''(''v''), the least weight of a path from ''q'' to ''v''.

#Next it reweights the edges of the original graph 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 ''s'', it runs [[Dijkstra's algorithm]] to find the shortest paths from ''s'' to each other vertex in the graph, using these modified weights to measure the length of each path.