我正在研究一个图形库。它必须有一个函数可以找到最分离的两个节点，即它们是从源节点到达目标节点之前需要遍历的最小节点数的最大数。
一种天真的方法是计算从每个节点到所有其他节点的分离程度，并对每个节点重复相同的操作。
事实证明，其复杂性是O(n^2)。
这个问题有什么更好的解决方案吗？
问问题
1607 次
2 回答
2
使用Floyd-Warshall 算法找到所有对的最短路径。然后遍历结果并找到具有最长路径的结果。
于 2013-01-15T10:56:08.377 回答
0
在图表上没有任何假设的情况下， Floyd-Warshall是要走的路。
如果您的图是稀疏的（即按节点计算的边相对较少，或者|E|<<|N|^2），那么Johnson可能会更快。
使用单位边权重（这似乎是您的情况），通过计算每个节点的最远节点（使用BFS）的幼稚方法导致O(|N|.|E|). 这可能可以进一步改进，但我现在看不到办法。
于 2013-01-15T13:23:14.603 回答