有没有一种算法来找到所有其他节点的每个节点的距离

-2

我想从所有其他节点获得所有节点的距离。例如，如果我有4个节点，那么我希望路径的距离为有没有一种算法来找到所有其他节点的每个节点的距离

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

即所有对那些可能

注：每个节点具有从所有其他节点的路径。

我的方法：我想过应用Dijkstra算法，但它适用于单一来源，然后我必须将其应用于每个节点作为来源，然后从它们中取出独特的对，其复杂度非常高。

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

来源

2016-11-04 Karan Nagpal

请包含您的'node'数据结构，以及您迄今尝试过的代码。 – brianpck

我参考了这里给出的代码。 http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/并仅为所有可能的节点运行dijkstra函数。 –

[Floyd-Warshall算法]（https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm） – dasblinkenlight

您可以试用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)的范围内完成。

来源

2016-11-04 19:45:21

有没有一种算法来找到所有其他节点的每个节点的距离

回答

相关问题