Peso minimo del bordo lungo un percorso

Question

Come troverei il massimo di un set di pesi minimi di bordo lungo tutto il percorso tra i vertici arbitrari (u,v)?

Stavo pensando una modifica di Floyd-Warshall?

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

.

Il peso minimo del bordo è 1

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

.

Il peso minimo del bordo è 3

Quindi il risultato è max(1, 3) = 3

Answer 1

Sì, una modifica di Floyd-Warshall funzionerebbe - Invece della lunghezza del percorso più breve, manterrai la traccia del percorso massimo "Larghezza".

Se sei interessato a due vertici, puoi prendere un approccio più semplice: iniziare con un grafico vuoto e aggiungere bordi ordinati dal loro peso (da alto a basso).Quando i nodi in questione vengono collegati, l'ultimo bordo aggiunto ti dà la massima "larghezza".Fatto correttamente (cioè utilizzando il disgiunto del disgiunto per verificare la connessione), questo sarà più veloce di Floyd-Warshall.

Nota: sto solo considerando pesi positivi.