algorithm - 如何为 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)，渐近最优。