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:
Notice that 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'':
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. IfThe weight of edges that belong to a shortest path from ''q'' to any node is zero, and therefore the lengths of the shortest paths from ''q'' to every node become zero in the reweighted graph; didhowever, notthey containstill remain shortest paths. Therefore, there can be no negative edges: if edge ''uv'' had a negative cycleweight after the reweighting, then duethe zero-length path from ''q'' to the''u'' waytogether thewith valuesthis edge would form a negative-length path from {{math|''h(v)q''}}wereto computed''v'', contradicting the fact that all modifiedvertices edgehave lengthszero distance from ''v''. areThe non-negative{{Citationexistence needed|date=Februaryof 2011}},negative edges ensuringensures 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.
