algorithm - 在连通图中找到所需的点

Question

有问题，我将其简化为如下问题:

在连通无向图中，边权重是从一端到另一端的时间。有些人站在某个顶点。现在，他们想集合在一起，找到一个地方(顶点)，在一定的时间T内，所有的人都会到达这个集合点。尽量减少这个 T。

如果您需要 margin 案例的更多信息:无负边缘；循环可能存在；同一个顶点可以停留不止一个人；顶点可能没有人；无向边，权重测量 u->v 或 v->u；人们从他们的初始位置开始；

如何高效地找到它？我是否应该为每个节点 v 计算 max(SPD(ui, v)) 其中 ui 是其他人的位置，然后在这些最大时间中选择最小的一个？有没有更好的办法？

Answer 1

我相信它可以在多项式运行时范围内完成，如下所示。在第一步中解决 All-Pairs Shortest Path problem得到所有顶点对应长度的最短路径矩阵；然后遍历行(或列)并选择用户所在的所有索引的最大条目所在的列。