그래프 이론 : 요르단 센터를 찾으시겠습니까?

Question

가중 그래프에서 다른 정점과의 거리를 최소화하는 정점 세트를 찾으려고합니다. Cursory Wikipedia 검색을 기반으로, 나는 이것을 요르단 센터. 그것을 찾기위한 좋은 알고리즘은 무엇입니까?

지금, 내 계획은 주어진 정점에서 나오는 각 지점의 무게 목록을 얻는 것입니다. 무게가 가장 작은 상대 차이를 가진 정점은 중심이 될 것입니다. 다른 아이디어가 있습니까?

Java를 사용하고 있지만 도움이되는 답변이 반드시 Java 특정 일 필요는 없습니다.

Answer 1

나는 먼저 Woluld를 사용한다 dijkstra 알고리즘 (각 언어에 대해 실행해야 함) 모든 verticles 사이의 가장 짧은 거리를 위해서는 다음과 같은보다 효율적인 알고리즘도 있습니다. 플로이드-와 찰리. 그런 다음 각 vm을 찾아야합니다. 가장 큰 다른 Verticles와의 거리는 DIJKSTRA 알고리즘 형태의 데이터 중 하나입니다. 그런 다음 VM이 가장 작은 Verticles는 그래프 센터에 있습니다. 의사 코드 :

int n = number of verticles;
int[][] D = RunDijkstraOrWarshall()
// D[a,b] = length of shortest path from a to b
int[] Vm = new int[n];
for(int i=0; i<n i++)
{
   Vm[i] = 0
   for(int j=0; j<n; j++) 
   {
     if (Vm[i] < D[i,j]) Vm[i] = D[i,j];
   }  
}

minVm = int.Max;
for(int i=0; i<n ;i++)
{
  if (minVm < Vm[i]) minVm = Vm[i];
}

for(int i=0; i<n ;i++)
{
  if (Vm[i] == minVm)
  {
     // graph center contans i
  }

}

Answer 2

그래프 센터 문제에 대한 세 가지 알고리즘 이이 MSC 논문에 나와 있습니다. 그래프 센터 문제에 대한 분산 알고리즘.

Answer 3

JGRAPHT 버전 1.1.0에서 시작하여 방법을 사용하면 GraphMeasurer.getGraphCenter(). 기본 코드는 가장 짧은 경로 방법을 사용합니다. 사용자는 그래프의 일부 특성 (예 : Sparse/Havense/...)에 따라 사용할 방법을 선택할 수 있습니다.