그래프에서 노드 그룹에 가장 가까운 노드를 찾는 방법은 무엇입니까?

Question

나는 평면이 아니어도 무 방향성, 비 가중 그래프가 있습니다. 또한 그래프의 노드 (실제 서브셋)의 서브 세트가 있고 서브 세트에 속하지 않은 노드를 찾아야합니다. 서브 세트의 모든 노드에 대한 거리의 최소 합계가 있어야합니다.

지금까지 나는 서브 세트의 각 노드에서 시작하여 호흡 우선 탐색을 구현했으며, 먼저 발생하는 교차점은 내가 찾고있는 노드입니다. 불행하게도, 그래프에는 많은 수의 노드가 포함되어 있으므로 너무 느리게 실행됩니다.

Answer 1

모든 쌍 최단 경로 알고리즘을 사용하면 O (V^3) 시간에 모든 노드의 거리를 찾을 수 있습니다 (Floyd-warshall 참조). 그런 다음 나중에 합계가 2 차 이상이 될 것이고 최악의 입방도 믿을 것입니다. 그것은 매우 간단하고 끔찍한 빠른 방법이지만, 지금 당장하고있는 것보다 훨씬 빠른 속도로 진행될 수 있습니다.