如何找到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），渐近最优。