问最小化图中的最大距离

EN

假设我们有一个加权的无向图。假设图中有N个节点(城市)，我们希望在城市中构建M (M<=N)个医院。现在我们需要选择最优的解决方案，这样从一个城市到一个有医院的城市的最大距离将被最小化。

假设我们有3个城市，我们需要建造1个医院。设有边1-3和2-3，权重分别为83和71。显然，最好的解决方案是在3号城市建立一家医院，因为这样最大距离将是83。

我的想法是使用弗洛伊德-沃肖尔算法，然后在距离数组中具有最小最大值的城市中建立一家医院。然后更新另一个数组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。那么我该如何解决这个问题？