如何找到路径的最大边将所有对MST

Question

的顶点作为我们假设我们有一个已知的最小生成树。

我们的任务是找出每对顶点之间存在路径上的最大优势。

举个例子，

我们有以下的最小生成树：

1---10---2 
     \  
     5\ 
      \ 
    4---4---3 

顶点1和2之间，我们与成本10 顶点1和3之间的边缘，我们具有成本5. 顶点3和4之间的边缘，我们有与成本的边缘4.

对于每个路径的最大边缘：

路径1-2：它仅包含与成本10分的边缘因此，答案是10

路径1-3：它仅包含与成本5.边缘因此，答案是5

路径1-4：从顶点1到顶点4，路径是1-3-4。它包含边缘成本5和边缘成本4.所以答案是5.

路径2-3：我们需要沿着路径2-1-3。最大边数为10.

路径2-4：我们需要沿着路径2-1-3-4。最大边缘10.

路径3-4：最大边缘4.

所以最终的答案将是：

X 10 5 5 
    X X 10 10 
    X X X 4 
    X X X X 

哪一个是该任务的最合适的算法？

到目前为止，我已经考虑过为每对顶点使用DFS的可能性。然而，由于我们有O（V^2）个顶点对，所以总的复杂度将是O（V^3），这看起来不太好。

Answer 1

对于每个顶点，您可以执行DFS来查找与该顶点相对应的行/列的矩阵条目。类似于

fill-entries-DFS(root, maxEdgeRootToV, v): 
    set the entry for (root, v) to maxEdgeRootToV 
    for each child w of v: 
     fill-entries-DFS(root, max(maxEdgeRootToV, edgeWeight(v, w)), w) 

for each vertex v: 
    fill-entries-DFS(v, -infinity, v) 

运行时间为O（V^2），渐近最优。