Floyd-Warshall para todos los pares

A veces necesita el camino más corto entre cada par de nodos, no solo desde un origen. Ese es el problema de todos los pares.

Floyd-Warshall completa una tabla de distancias para todos los pares mediante tres bucles anidados y ordenados, con muy poca configuración.

Use una matriz donde dist[i][j] sea el menor costo conocido de i a j. Inicialícela con las aristas directas proporcionadas.

Cada nodo puede llegar a sí mismo de forma gratuita, así que establezca en cero la diagonal dist[i][i] antes de comenzar a relajar.

El truco consiste en permitir que los caminos pasen por un nodo intermedio k y comprobar si pasar por k es más barato que ir directamente.

El bucle externo es k, el punto intermedio elegido. Los bucles internos i y j prueban cada par con respecto a ese punto intermedio.

Para cada par, relaje pasando por k: si ir de i a k y luego a j es más corto, actualice dist[i][j] con ese costo combinado.

Cuando termina k, todos los pares pueden usar nodos intermedios hasta k. Colocar k en el bucle externo mantiene correcta esa garantía.

Floyd-Warshall admite aristas negativas, pero no ciclos negativos. Un ciclo negativo deja alguna entrada de la diagonal por debajo de cero.

Tres bucles sobre n nodos producen un tiempo de O(n^3) y un espacio de O(n^2), algo práctico solo cuando n se mantiene en unos pocos cientos.

Elija Floyd-Warshall cuando el grafo sea pequeño y denso y realmente necesite la distancia entre cada par, no solo desde un único origen.

Inicialice una matriz, establezca la diagonal en cero y luego recorra k, i, j para relajar pasando por k. Caminos más cortos entre todos los pares en O(n^3). 🧮