图论：找到乔丹中心？

发布于 2024-08-12 20:17:10 字数 248 浏览 3 评论 0原文

我试图找到一组顶点，使它们与加权图上其他顶点的距离最小。根据粗略的维基百科搜索，我认为这被称为乔丹中心。有哪些好的算法可以找到它？

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

甩你一脸翔 2024-08-19 20:17:10

我首先使用 Dijkstra 算法（必须为每个顶点运行）来计算最短所有顶点对之间的距离 - 还有一些更有效的算法，例如 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
  }

}

I woluld first use Dijkstra algorithm (it has to be run for each verticle) for computng shortest distances between all pairs of verticles - there are also some more efficient algorithms for that like Floyd-Warshall. Then for each verticle V you have to find Vm - the largest distance to any other verticles amongs the data retuirned form Dijkstra algorithm. Then, the verticles with the smallest Vm are the one in the graph center. Pseudocode:

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
  }

}

回复收藏 0 原文