java - グラフ理論：ヨルダンの中心を見つけますか？

Question

重み付きグラフで他の頂点までの距離を最小化する頂点のセットを見つけようとしています。大雑把なウィキペディア検索に基づいて、これはジョーダンセンターと呼ばれていると思います。それを見つけるためのいくつかの良いアルゴリズムは何ですか？

今のところ、私の計画は、特定の頂点から発生する各ブランチの重みのリストを取得することです。重みの相対差が最も小さい頂点が中央の頂点になります。他のアイデアはありますか？

私はJavaを使用していますが、役立つ回答は必ずしもJava固有である必要はありません。

Answer 1

私は最初にダイクストラアルゴリズム（各頂点に対して実行する必要があります）を使用して、頂点のすべてのペア間の最短距離を計算します-Floyd -Warshallのようなより効率的なアルゴリズムもいくつかあります。次に、各バーティクルVについて、Vmを見つける必要があります。これは、ダイクストラアルゴリズムから取得されたデータの中で他のバーティクルまでの最大距離です。次に、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

この修士課程では、グラフ中心問題の3つのアルゴリズムが示されています。グラフ中心問題の分散アルゴリズム。

Answer 3

JGraphTバージョン1.1.0以降では、メソッドを使用するだけで済みますGraphMeasurer.getGraphCenter()。基礎となるコードは最短経路法を使用します。ユーザーは、グラフのいくつかの特性（たとえば、スパース/デンス/ ...）に応じて、使用する方法を選択できます。