在图中，如何找到一组节点的最近节点？

Question

我有一个无向图，它不必是平面的。我也有一个图的节点子集（真子集），我需要找到一个不属于子集的节点，并且与子集中所有节点的距离最小。

到目前为止，我已经从子集中的每个节点开始执行呼吸优先搜索，而首先发生的交集就是我正在寻找的节点。不幸的是，由于图形包含大量节点，所以运行速度太慢。

Answer 1

全对最短路径算法允许您在O（V^3）时间内找到所有节点之间的距离，请参见Floyd-warshall。然后求和后至少是二次的，我认为最坏的情况也是立方的。这是一种非常简单而不是非常快速的方式，但它听起来可能比你现在正在做的要快一个数量级。