我有一个无向的、未加权的图,它不必是平面的。我还有一个图节点的子集(真正的子集),我需要找到一个不属于该子集的节点,并且到子集中所有节点的距离总和最小。
到目前为止,我已经实现了从子集中的每个节点开始的呼吸优先搜索,首先出现的交叉点就是我要寻找的节点。不幸的是,由于图表包含大量节点,因此运行速度太慢。
全对最短路径算法允许您在 O(V^3) 时间内找到所有节点之间的距离,请参阅Floyd-warshall。然后之后求和至少是二次的,我相信最坏的情况也是三次的。这是一种非常简单且不是非常快速的方法,但听起来它可能比您现在正在做的要快一个数量级。