最短経路アルゴリズム：複数のソース、最も近い宛先

Question

ベルマンフォードアルゴリズムやダイクストラのアルゴリズムのようなアルゴリズムは、グラフ上の単一の開始頂点から他のすべての頂点までの最短経路を見つけるために存在します。それらの複数のソースバージョンは、すべてのエッジを逆転させ、宛先を開始ノードとして扱うことによって達成することができる。

私は「合意」に「公正」のパスを見つけること、グラフ上のソースの「重心」、ソースのセットに「最も近い」ですすなわち頂点を見つけるために、それを拡張したいと思います頂点。

すでにアルゴリズムがありますか？彼らは何ですか？

Answer 1

Floyd–Warshall algorithm

は、私はあなたがの "グ​​ラフの偏心" を計算したいと思うソース（S1、S2、... Sn-1に、Sn）の。

1. Floyd-Warshallアルゴリズムを使用して、グラフの最短経路のすべてのペアを計算します。
2. （d [v、S1] + d [v、S2] + d [v、S3] ... d [v、Sn-1]の最小合計であるグラフの結果ノードVを見つける。 + D〔V、Snの]）

詳細情報：たぶん距離グラフG（V、E）に存在ノードvを求める

Graph Eccentricity

UPDATE

〜Sはすべて同じですが現実主義者ではありませんIC。 d [v、S1]、d [v、S2]、d [v、S3] .... d [v、Sn-1]、d [v、Sn]のスタンド偏差を計算することができます。あなたが選んだ特定の値よりも小さく、0より大きくかつ等しい値。