如何找到路徑的最大邊將所有對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），漸近最優。