图论：如何找到约旦中心？

Question

我正在尝试找到一组顶点，使它们与加权图上的其他顶点之间的距离最小。根据维基百科的初步搜索结果，我认为这被称为Jordan Center。有哪些好的算法可以找到它？

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

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

- Nick Heiner

Answer 1

我首先会使用Dijkstra算法（必须对每个顶点进行运行）来计算所有顶点之间的最短距离 - 还有一些更有效率的算法，例如Floyd-Warshall。然后，对于每个顶点V，您需要找到Vm - 从Dijkstra算法返回的数据中任何其他顶点到V之间的最大距离。然后，具有最小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
  }

}

- PanJanek

---

我相信你的意思是要检查 "if (Vm[i] < D[i, j]) Vm[i] = D[i, j])"。按照你的方式，Vm[i] 将始终为零。你想要检查 "如果从 i 到 j 的距离大于我迄今为止看到的从 i 到其他某个顶点的最大距离...将最大距离更改为从 i 到 j 的距离"。 - Tom

除此之外你需要做的更改...解释得非常好 :-). 代码可以再整理一下，但它很好地说明了概念并用语言解释了你所写的内容 :-). +1. - Tom

谢谢你发现了这个问题，我已经进行了修正。上述的算法可以直接整合到Dijkstra或Floyd-Warshal中，以避免运行额外的循环（因为Dijkstra必须无论如何迭代顶点）。 - PanJanek

Answer 2

本硕士论文提出了三种图中心问题算法：图中心问题的分布式算法。

- miku

Answer 3

从JGraphT版本1.1.0开始，您可以直接使用方法GraphMeasurer.getGraphCenter()。底层代码使用了最短路径算法。用户可以根据图的某些特征（如稀疏/密集/...）选择使用哪种方法。

- Joris Kinable