私は現在、次の問題に取り組んでいます: 有向グラフG = ( V , E ) が与えられた場合、ダイクストラのアルゴリズムを使用して、開始ノードv 0から各ノードv i ∈ Vの最短距離d iを見つけます。
ここで、このノードからのすべてのノードの最短距離 ∑<em>d iの合計が最小になるノード *v** を見つけたいと思います。
次の例では、開始ノードv 0は黄色で、明らかに距離が 0 です。他のすべてのノードの最短距離が示されています。
最初の図 (左下の開始ノード) では、すべての最短距離の合計は
∑<em>d i = 1+2+2+2+3+3+3 = 16
2 番目の図 (中央の開始ノード) では、すべての最短距離の合計は
∑<em>d i = 1+1+1+2+2+2+2 = 11
エッジの重みは float です。この例では、簡単にするために 1 が選択されています。
もちろん、すべてのノードで最小値を見つけようとすることもできますが、もちろんそれは遅すぎます。あなたのアイデアを聞くのが待ちきれません！:-)
ソーシャルネットワークの文脈では、あなたが説明する中心性の指標は、1966年にSadibussiによって定義されました（ここまたは非公式のリンクはこちらを参照してください。分散性の尺度として、ここ（p.225）のフリーマンによっても説明および推奨されています）。ファーネスと呼ばれることもあります (こちらを参照)。
幅優先探索では、グラフ上のすべての頂点から他のすべての頂点への最短経路の長さを計算できます。こことここで受け入れられた回答を参照してください。All-Pairs Shortest Paths を計算するその他の方法については、こちらで説明しています。
編集：
あなたは近似解に興味があると指摘したので、Baswana と Kavitha による次の論文を見てください。表 1.1 は既知の結果をまとめたものです。これまでの最適な近似解では、3 ストレッチ ソリューションに O(n^(3/2)) のスペースが必要です (つまり、推定距離は実際の距離よりも長くなりますが、実際の距離の 3 倍未満になります)。これは、ほとんどの実用的な目的には十分ではないと思います。既知の APASP (All-Pairsapproximate Shortest Paths) アルゴリズムは、stretch<3 で O(n^2) 未満のスペース要件を持ちません。
実用的な解決策:
ほとんどの実装では、現実世界の道路網に固有の階層を利用しています。たとえば、 this、this、およびthisを参照してください。