= Minimum-hop shortest paths
{title2=$\min_{\rm lex}(\text{weight},\text{edge count})$}
Among paths of minimum total weight, choose the fewest edges. Store a <lexicographic order> pair $(d,h)$ and extend it across weight $w$ as $(d+w,h+1)$. For positive edge weights, every extension strictly increases its first component, so <Dijkstra's algorithm> settles these pairs correctly when its <priority queue> and relaxation both compare the full pair. Equal total weight then selects the smaller hop count; arbitrary vertex-name tie-breaking does not express this objective.
Back to article page
