Johnson's algorithm: Difference between revisions

Revision as of 00:53, 5 January 2011

Revision as of 05:50, 22 February 2011

Line 13:

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

In the reweighted graph, all paths between a pair {{math|''s''}} and {{math|''t''}} of nodes have the same quantity {{math|''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. IfThe theprevious graphstatement didcan notbe containproven aas negativefollows: cycle,Let thenp duebe toan the way the values {{math|''h(v)''}} were computed, all modified edge lengths are nons-negative,t ensuringpath. the optimality of the paths found by DijkstraIt's algorithm.weight The distancesW in the originalreweighted graph mayis be calculated from the distances calculatedgiven by Dijkstra's algorithm in the reweightedfollowing graph by reversing the reweighting transformation.expression:

[w(s, p1) + h(s) - h(p1)] + [w(p1, p2) + h(p1) - h(p2)] + ... + [w(p_n, t) + h(p_n) - h(t)]

Notice that every +h(p_i) is cancelled by -h(p_i) in the previous bracketed expression; therefore, we are left with the following expression for W:

[w(u, p1) + w(p1, p2) + ... + w(p_n, t)]+ h(s) - h(t)

Notice that the bracketed expression is the weight of p in the original weighting.

Since the reweighting adds the same amount to the weight of every s-t path, a path is a shortest path in the original weighting if and only if it is a shortest path after reweighting. If the graph did not contain a negative cycle, then due to the way the values {{math|''h(v)''}} were computed, all modified edge lengths are non-negative{{fact}}, 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.

==Analysis==