Minimum de pondération de bord le long d'un chemin

Question

Comment faire pour en trouver le maximum d'un ensemble minimum de bord des poids le long de tous les possibles chemin entre l'arbitraire des sommets (u,v)?

Je pensais à une modification de Floyd-Warshall?

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

Minimale du bord de poids est de 1

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

Minimum de pointe poids est de 3

Ainsi, le résultat est max(1, 3) = 3

Answer 1

Oui, une modification de Floyd-Warshall ne fonctionne - au lieu de la plus courte longueur de chemin d'accès, vous allez garder une trace de l'maximale du chemin d'accès "largeur".

Si vous êtes intéressé seulement par les deux sommets, vous pouvez prendre une approche plus simple:commencez avec un graphique vide et ajouter les bords commandés par leur poids (de haut en bas).Lorsque les nœuds en question est connecté, le dernier bord ajoutée vous donne le maximum de "largeur".Fait correctement (c'est à direà l'aide disjoints ensemble afin de vérifier l'existence de liens), ce sera plus rapide, puis de Floyd-Warshall.

Note:Je suis seulement en considérant positif de poids.