Revision as of 06:45, 22 February 2011 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,640 edits m →Algorithm description: typo ← Previous edit		Revision as of 06:45, 22 February 2011 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,640 edits →Algorithm description: split section 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. ==Correctness== 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. The previous statement can be proven as follows: Let p be an s-t path. It's weight W in the reweighted graph is given by the following expression:

Johnson's algorithm: Difference between revisions