Peso mínimo del borde a lo largo de una trayectoria

Question

Cómo encontraría el máximo de un conjunto de pesos mínimos de borde a lo largo de todas las rutas posibles entre vértices arbitrarios (u,v)?

¿Estaba pensando en una modificación de Floyd-Warshall?

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

El peso mínimo del borde es 1

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

El peso mínimo del borde es 3

Por lo tanto, el resultado es max(1, 3) = 3

Answer 1

Sí, una modificación de Floyd-Warshall funcionaría: en lugar de la longitud de la ruta más corta, realizará un seguimiento del "ancho"máximo de la ruta.

Si solo está interesado en dos vértices, puede adoptar un enfoque más simple:comience con un gráfico vacío y agregue bordes ordenados por su peso (de mayor a menor).Cuando los nodos en cuestión se conectan, el último borde agregado le da el "ancho" máximo.Hecho correctamente (i. e.usando un conjunto disjunto para verificar la conectividad), esto será más rápido que Floyd-Warshall.

Nota:Solo estoy considerando pesos positivos.