Johnson's algorithm: Difference between revisions

Revision as of 22:55, 27 February 2023

Revision as of 00:03, 24 April 2024

Line 32:

In the reweighted graph, all paths between a pair {{mvar|s}} and {{mvar|t}} of nodes have the same quantity {{math|''h''(''s'') − ''h''(''t'')}} added to them. The previous statement can be proven as follows: Let {{mvar|p}} be an {{tmath|s-t}} path. Its weight W in the reweighted graph is given by the following expression:

:<math display="block">\biglleft(w(s, p_1) + h(s) - h(p_1)\bigrright) + \biglleft(w(p_1, p_2) + h(p_1) - h(p_2)\bigrright) + ... + \biglleft(w(p_n, t) + h(p_n) - h(t)\bigrright).</math>

Every <math>+h(p_i)</math> is cancelled by <math>-h(p_i)</math> in the previous bracketed expression; therefore, we are left with the following expression for ''W'':

:<math display="block">\biglleft(w(s, p_1) + w(p_1, p_2) + ...\cdots + w(p_n, t)\bigrright)+ h(s) - h(t)</math>

The bracketed expression is the weight of ''p'' in the original weighting.