图论:找到乔丹中心？

Question

我正在尝试找到一组顶点,这些顶点最小化了它们与加权图上其他顶点的距离.基于粗略的维基百科搜索,我认为这被称为约旦中心.有什么好的算法可以找到它？

现在,我的计划是获取从给定顶点发出的每个分支的权重列表.权重具有最小相对差异的顶点将是中心的.还有其他想法吗？

我正在使用Java,但有用的答案不一定需要特定于Java.

Answer 1

我首先使用Dijkstra算法(必须为每个Verticle运行)来计算所有Verticle对之间的最短距离 - 对于像Floyd-Warshall这样的算法也有一些更有效的算法.然后,对于每个垂直V,您必须找到Vm - 与Dijkstra算法重新训练的数据之间的任何其他Verticle的最大距离.然后,具有最小Vm的Verticle是图中心的Verticle.伪代码:

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
  }

}