问最小生成树的全对最短路径

EN

正如@Codor所述，在MST中，任何一对节点都只有一条唯一的路径b/w，最短路径也是相同的。为了计算最短路径b/w所有对。您可以选择遵循此算法。

• 您基本上可以通过不断移除叶节点来选择MST的根，直到只剩下一个或两个节点。 复杂性：树中的中心节点 --这可以在O(V)即线性时间内实现
• 选择其中之一作为根。使用宽度优先搜索(BFS)计算所有其他节点相对于根节点的距离。 复杂度: O(V+E) ~ O(V)在树的情况下
• 现在，您可以找到距离b/w，任何一对节点都称其为a，b。查找其最小共同祖先(lcp)。那么有两种情况如果

1. lcp(a,b) = r (root of the tree). dis(a,b) = dis[a] + dis[b]
2. lcp(a,b) = c ( which is not the root node) dis(a,b) = dis[a] + dis[b] - 2 \* dis[c] 

​

其中dis(x，y) =距离b/w节点x，y和disx节点x从根节点的距离，如果使用排名联合查找

复杂度: O(h)，其中h是每对(a，b)树的高度。H= X/2，其中X是树的直径。因此，完全的复杂性取决于no。叶节对。