问如何求mst中所有顶点对的最大路径边

EN

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

我们的任务是找到每对顶点之间存在的路径的最大边。

举个例子，

我们有以下最小生成树：

    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)，这看起来并不好。