全ての道路を使えるときの、都市 \(1\) から都市 \(i\) までの最短距離を \(D_i\) とします。廃道にする道路をどのように選んでも、明らかに \(d_i\geq D_i\) が成り立つため、もし全ての \(i\) で \(d_i=D_i\) を満たすような道路の選び方が存在すれば、それが最適解となります。実はそのような選び方が必ず存在します。

各 \(i=2,3,\ldots,N\) について「都市 \(1\) から都市 \(i\) の最短経路において、都市 \(i\) に到達する直前に使った道路」をそれぞれ残せば十分です。\(d_i=D_i\) が達成されることの証明は、経由する道路の本数に関する帰納法によります。

ダイクストラ法を用いて、各都市に到達する直前の道路を記録することで求めることができます。

実装例(C++)