他のすべてのノードからすべてのノードまでの距離を見つけるアルゴリズムはありますか？

Question

他のすべてのノードからすべてのノードまでの距離を取得します。例えば、私は4つのノードを持っている場合、私はパスの距離を望む

（1,2）、（1,3）、（1,4）、（2,3）、（2,4）、（3） 、4）

すなわち可能なすべてのペア

注：すべてのノードが他のすべてのノードからのパスを持っています。

私のアプローチ：Dijkstraのアルゴリズムを適用することを考えましたが、それは単一のソースで動作し、ソースとしてすべてのノードに適用し、非常に複雑なものからユニークなペアを取り出す必要があります。

編集： 最小限のスパニングツリーがあり、同じタスクを実行する必要がある場合はどうなりますか？ あるノードから他のノードへのパスが1つしかないことを意味します。

Answer 1

Floyd–Warshall algorithmで試すことができます。
時間複雑度はO(V^3)です。ここで、Vはノードの数です。

ウィキペディアからの擬似コード：

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 
2 for each vertex v 
3 dist[v][v] ← 0 
4 for each edge (u,v) 
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 
6 for k from 1 to |V| 
7 for i from 1 to |V| 
8  for j from 1 to |V| 
9   if dist[i][j] > dist[i][k] + dist[k][j] 
10    dist[i][j] ← dist[i][k] + dist[k][j] 
11   end if 

---

あなたは木を使用している場合は、単に各ノードのBFSを作ります。これは、O(V*(V+E))を取る、実際にはO(V^2)です。E = V-1からです。

出力（すべてのペアの距離）のサイズがV*(V-1)なので、これはO(V^2)未満では実行できません。