假设我们有一个带权无向图。假设图中有N个节点（城市），我们想在城市中建立M个医院（M<=N）。现在我们需要选择最优解，使得距离城市的医院最远的城市之间的最大距离最小。
假设我们有3座城市，并且我们需要建造1座医院。让1-3和2-3这两条边存在，其权值分别为83和71。显然，最优的解是在城市3建立医院，因为这样最大的距离是83。
我的想法是使用Floyd-Warshall算法，然后在距离数组中具有最小max值的城市中建立医院。然后更新另一个数组b，以便b1显示从城市1到拥有医院的城市的最小距离，并类似地定义bi。之后，我想按以下方式更新距离值：
在弗洛伊德-沃舍尔算法之后，距离表将如下所示：
显然，现在最好在城市6建造医院，因为最大值将会是6。现在更新数值：
但是我们现在不确定是在城市3还是城市4建立医院。如果我们在城市4建立医院，那么更新表格后，我们会发现需要在城市1建立医院，最大距离为2。
但是如果我们在城市3建立医院并更新数值，我们会发现最好在城市4或城市5建立医院。但无论哪种情况，最大值都将是3。那么我该如何解决这个问题呢？
假设我们有3座城市，并且我们需要建造1座医院。让1-3和2-3这两条边存在，其权值分别为83和71。显然，最优的解是在城市3建立医院，因为这样最大的距离是83。
我的想法是使用Floyd-Warshall算法，然后在距离数组中具有最小max值的城市中建立医院。然后更新另一个数组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
在弗洛伊德-沃舍尔算法之后，距离表将如下所示：
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。那么我该如何解决这个问题呢？