= Minimum-hop dominance for nearly unit weights
For a graph on $n$ vertices with all edge weights in $[1,1+1/n]$, every minimum-weight <shortest path> has the smallest possible number of edges. Indeed, positivity permits a simple optimum, and a simple $r$-edge path weighs at most $r+r/n<r+1$ for $r\leq n-1$, while any path with more edges weighs at least $r+1$. A <breadth-first search> followed by weighted <dynamic programming> along increasing-hop edges therefore solves the single-source problem in $O(|V|+|E|)$ time. Choosing an arbitrary breadth-first tree alone is insufficient: equal-hop routes may still have different weights.
Back to article page
