Revision as of 20:29, 28 December 2010 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,640 edits Suurballe's algorithm; {{math}} ← Previous edit		Revision as of 20:47, 3 January 2011 edit undo 158.64.104.98 (talk) →Algorithm description Next edit →
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. ~~However~~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, 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==

Johnson's algorithm: Difference between revisions