首页 文章

是否有算法来查找每个节点与所有其他节点的距离[重复]

提问于
浏览 次
-2

这个问题在这里已有答案：

我想从所有其他节点获得所有节点的距离 . 例如，如果我有4个节点，那么我想要路径距离

（1,2），（1,3），（1,4），（2,3），（2,4），（3,4）

即所有可能的对

注意：每个节点都有一个来自其他每个节点的路径 .

我的方法：我考虑应用Dijkstra的算法，但它适用于单个源，然后我必须将它作为源应用于每个节点，然后从它们中取出具有非常高复杂度的唯一对 .

编辑：如果我有一个最小生成树并且必须执行相同的任务会是什么情况？我的意思是从一个节点到另一个节点只有一条路径 .

algorithm graph dijkstra

1 回答

  • 0

    你可以试试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) 内完成 .

    回复于

相关问题