图论:找到乔丹中心？

Question

我正在尝试寻找一组顶点，使它们与加权图上其他顶点的距离最小。根据维基百科的粗略搜索，我认为这被称为Jordan Center。有什么好的算法可以找到它？

现在，我的计划是获得来自给定顶点的每个分支的权重列表。权重具有最小相对差异的顶点将成为中心顶点。还有其他想法吗？

我使用的是Java，但有帮助的答案不一定是特定于Java的。

Answer 1

我会首先使用Dijkstra algorithm (它必须为每个顶点运行)来计算所有顶点对之间的最短距离-还有一些更有效的算法，比如Floyd-Warshall。然后，对于每个顶点V，你必须找到Vm -在数据返回形式Dijkstra算法中到任何其他顶点的最大距离。然后，具有最小Vm的顶点是位于图中心的顶点。伪码：

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

本文提出了解决图中心问题的三种算法：A distributed algorithm for the graph center problem算法。

Answer 3

从JGraphT版本1.1.0开始，您可以简单地使用GraphMeasurer.getGraphCenter()方法。底层代码使用最短路径方法。用户可以根据图形的某些特性(例如稀疏/密集/...)来选择要使用的方法。