c++ - 给定有向图和商店位置放置商店，以便从任何城市到最近商店的最大距离最小化

Question

我有一组城市 1-C，一组连接它们的道路，以及一组现有商店。道路是双向的，距离是给定的。我想要找到的是放置商店的最低城市编号，以便任何城市与最近的商店之间的最大距离最小化。

到目前为止，我所做的是构建所有城市的邻接矩阵，其中包含边权重。然后，我对此运行 floyd-warshall 以生成一个矩阵，其中包含从每个顶点到其他顶点的所有最短路径。

在这之后我有点迷路了。我所做的是使用矩阵找到每个不是商店的顶点到每个其他不是商店的顶点的最大最小距离。然后我选择所有这些中的最小值。然而，这是不正确的。我不确定我是否走在正确的道路上。

任何输入都会很棒。或者，如果您能指出类似的问题，那就太好了。谢谢!

如果重要的话，我正在用 C++ 实现。

Answer 1

运行 Floyd-Warshall。现在你有所有城市对的 Distance[i, j] == Distance[j, i]。

然后，为每个城市 i 找到 DistanceToNearestStore[i]。如果城市 i 有商店，则为 0。否则，对于每个城市 j，找到最小的 Distance[i, j]，其中 j 有一家商店。

现在，我们找到 DistanceToNearestStore[i] 的最大值 - 我们称它为 MaxDistanceToNearestStore。这是我们希望通过添加一家商店来最小化的。

现在我们尝试在每个城市开设一家商店，看看哪一家的结果最好:

for each city s:
    maxDistanceToNearestStoreWithStoreInS = 0
    for each city i:
        cityDistanceToNearestStore = min(DistanceToNearestStore[i], Distance[i, s])
        maxDistanceToNearestStoreWithStoreInS = max(maxDistanceToNearestStoreWithStoreInS, cityDistanceToNearestStore)
    if (maxDistanceToNearestStoreWithStoreInS < MaxDistanceToNearestStore)
        MaxDistanceToNearestStore = maxDistanceToNearestStoreWithStoreInS
        bestCity = s

bestCity 是您应该在其中开设商店的城市。