重み付き無向グラフがあるとしましょう。グラフに N 個のノード (都市) があり、都市に M (M<=N) 個の病院を建設したいとします。次に、都市から病院のある都市までの最大距離が最小になるように、最適なソリューションを選択する必要があります。
3 つの都市があり、1 つの病院を建設する必要があるとします。重みがそれぞれ 83 と 71 のエッジ 1-3 と 2-3 があるとします。明らかに最適な解決策は、都市 3 に病院を建設することです。その場合、最大距離は 83 になります。
私のアイデアは、Floyd-Warshall アルゴリズムを使用して、距離配列の最大値が最小の都市に病院を建設することでした。次に、別の配列 b を更新して、b1 が都市 1 から病院のある都市までの最小距離を示し、bi を同様に定義します。その後、次のように距離値を更新したいと思います。
dist_i_j = min (dist_i_j, b_j)
M 病院をすべて建設するまで、これを繰り返します。
しかし、このアルゴリズムが問題に遭遇するケースがいくつかあります。このグラフが与えられ、3 つの病院を建設する必要があるとします。
edge 1-2 with distance 1
edge 1-3 with distance 2
edge 2-4 with distance 7
edge 2-6 with distance 3
edge 3-4 with distance 5
edge 4-5 with distance 2
edge 5-6 with distance 4
Floyd-Warshall アルゴリズムの後、距離テーブルは次のようになります。
0 1 2 7 8 4
1 0 3 7 7 3
2 3 0 5 7 6
7 7 5 0 2 6
8 7 7 2 0 4
4 3 6 6 4 0
最大値が 6 になるため、病院を都市 6 に建設するのが最善であることは明らかです。値を更新します。
0 1 2 6 4 0
1 0 3 6 4 0
2 3 0 5 4 0
4 3 5 0 2 0
4 3 6 2 0 0
4 3 6 6 4 0
しかし、都市 3 と都市 4 のどちらに病院を建設するかはわかりません。都市 4 に病院を建設する場合、テーブルを更新すると、都市 1 に病院を建設する必要があることがわかり、最大距離は次のようになります。 2になります。
しかし、都市 3 に病院を建設し、値を更新すると、都市 4 または都市 5 に病院を建設するのが最善であることがわかります。しかし、どちらの場合も、最大値は 3 になります。