私は、重み付けされたグラフ上の他の頂点との距離を最小にする頂点のセットを見つけようとしています。わかりやすいウィキペディア検索に基づいて、これはJordan Centerと呼ばれています。それを見つけるための良いアルゴリズムは何ですか？グラフ理論：ヨルダンの中心を見つけるか？
私の計画は、与えられた頂点から出ている各ブランチの重みのリストを取得することです。重みが最小の相対差を持つ頂点は中央のものになります。他のアイデア？
私はJavaを使用していますが、有用な回答は必ずしもJava固有である必要はありません。
すべての対の頂点の間の最短距離を計算するために、最初にDijkstra algorithm（それは各頂点に対して実行する必要があります）を使用します。さらに、Floyd-Warshallのようなより効率的なアルゴリズムがあります。その後、各VのVmについて、の最大値を、Dijkstraアルゴリズムのデータ再構成形式の中から他の頂点までの距離を求めなければなりません。そして、Vmが最も小さい頂点がグラフ中心の頂点となる。擬似コード：JGraphTバージョン1.1.0から始まっ
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
}
}
このMSC論文では、グラフ中心の問題の3つのアルゴリズムが示されています。A distributed algorithm for the graph center problem。
、あなたは単にメソッドGraphMeasurer.getGraphCenter()を使用することができます。基礎となるコードは、最短パスメソッドを使用します。ユーザは、グラフのいくつかの特性（例えば、疎/濃/ ...）に応じて、使用する方法を選択することができる。
"if（Vm [i]
Tom
あなたが作る必要があるその変更以外の...良い説明:-)。コードはちょっと整理できますが、概念を説明し、あなたが単語で書いたことを説明するのはうまくいきます:-)。 +1。 – Tom
それを見つけてくれてありがとう、私はちょうど修正した。上記のアルゴリズムは、Dijksta、Floyd-Warshalに組み込むことができ、余分なforループを回避することができます（DijkstraはいつでもVertexを反復処理する必要があります）。 – PanJanek