= Integer-weight shortest-path tie-breaking lemma
{title2=$w'(e)=|V|w(e)+1$}
In a finite graph with positive integral <edge> weights, replacing $w(e)$ by $|V|w(e)+1$ makes every transformed <shortest path> minimise original weight first and <edge> count second. Positive weights imply that an optimal route is simple, with at most $|V|-1$ <edges>. Original integral path weights that differ have a gap of at least one; multiplication by $|V|$ outweighs every possible difference in simple-path <edge> counts. Among equal-weight paths, only the added <edge> count differs. Thus a single ordinary <shortest path> computation solves lexicographic weight-and-hop minimisation.
Back to article page
