= Solution
Let $N=|V|$ and replace every <edge> weight by \b[$w'(e)=Nw(e)+1$]. Call the supplied shortest-path routine once using these new weights, and return its path in the original graph. For every path $P$,
$$
w'(P)=Nw(P)+|P|,
$$
where $|P|$ is its number of <edges>. Positive original weights imply positive transformed weights, so a shortest route can be taken to be simple and has at most $N-1$ <edges>. Distinct integral original weights of paths differ by at least one. Thus if $w(P)<w(Q)$ for simple paths, then
$$
w'(Q)-w'(P)=N\bigl(w(Q)-w(P)\bigr)+|Q|-|P|\ge N-(N-1)>0.
$$
For equal original weights, the transformed comparison is exactly the comparison of hop counts. Therefore every transformed shortest path minimises original weight first and number of <edges> second, proving the <integer-weight shortest-path tie-breaking lemma>. The transformation costs $O(N+|E|)$ time, followed by one subroutine call. Weights gain only $O(\log N)$ bits; exact arithmetic should be used if multiplying machine-sized weights might overflow. If $t$ is unreachable, it remains unreachable.
Back to article page
