Comment trouver le bord maximal du chemin pour toutes les paires de sommets de mst

Question

Supposons que nous ayons un arbre recouvrant minimum connu.

Notre tâche consiste à trouver l'arête maximale pour le chemin qui existe entre chaque paire de sommets.

Pour donner un exemple,

Nous avons l'arbre minimum suivant:

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

Entre sommet 1 et 2, nous avons un avantage avec un coût 10. Entre sommet 1 et 3, nous ont un avantage avec un coût 5. Entre le sommet 3 et 4, nous avons un avantage avec un coût 4.

bord maximum pour chaque chemin:

chemin 1-2: Il ne contient que le bord avec un coût 10. Donc, la réponse est 10.

chemin 1-3: Il ne contient que le bord avec un coût 5. La réponse est 5.

chemin

1-4: Pour aller du sommet 1 au sommet 4, le chemin est 1-3-4. Il contient le bord avec le coût 5 et le bord avec le coût 4. Donc la réponse est 5.

chemin 2-3: Nous devons suivre le chemin 2-1-3. La limite maximale est 10.

chemin 2-4: Nous devons suivre le chemin 2-1-3-4. Maximum 10. bord

chemin

3-4: Maximum bord 4.

La réponse finale serait:

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

Lequel est l'algorithme le plus approprié pour cette tâche? Jusqu'ici, j'ai considéré la possibilité d'utiliser DFS pour chaque paire de sommets. Cependant, puisque nous avons O (V^2) paires de sommets, la complexité totale serait O (V^3), ce qui ne semble pas bon.

Answer 1

Pour chaque sommet, vous pouvez faire en sorte que DFS trouve les entrées de la matrice pour la ligne/colonne correspondant à ce sommet. Quelque chose comme

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) 

Le temps d'exécution est O (V^2), l'optimum asymptotique.