アルゴリズム：州のすべての都市を州の2つの空港のいずれかに接続するための道路の最短距離

Question

州は10都市A、B、C、D、E、F、G、H 、I、J。さて、DとGの両方に空港があるとしましょう。各都市間の距離を考えれば、すべての都市が空港につながるように建設されるべき道路の最短距離はいくらですか？各都市から空港への直接ルートまたは間接ルートがあります（つまり、他の都市を経由して）。私たちの目的は最小限の道路長を構築することです。

Answer 1

問題はになります。重みがゼロのエッジがある空港に関連付けられた頂点を単純に連鎖させることで問題は軽減されます。したがって、たとえば次のようにして解決できます。古典プリムのアルゴリズム：

1. は、すべての頂点がカバーされるまで、スパニングツリー
2. 反復を強化する最も安いものを選択し、残りのすべてのエッジの中、空港
3. を含む全ての頂点とソリューションを初期化します。