假设我们有一个加权无向图。假设图中有 N 个节点（城市），我们要在城市中建立 M（M<=N）家医院。现在我们需要选择最优解，使得一个城市到一个有医院的城市的最大距离最小。
假设我们有 3 个城市，我们需要建造 1 家医院。假设有边 1-3 和 2-3，权重分别为 83 和 71。显然，最佳解决方案是在城市 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。那么我该如何克服这个问题呢？