Calculadora Floyd-Warshall

Pseudocódigo

Tres bucles anidados y una sola línea de actualización. Toda la sutileza está en el orden de los bucles: k debe ser el bucle más externo, y equivocarse en eso es el fallo clásico.

FloydWarshall(grafo):
    dist = matriz V por V, todo infinito
    para cada vértice v:     dist[v][v] = 0
    para cada arista (u,v,w): dist[u][v] = w

    para k en vértices:              // intermedio
        para i en vértices:          // origen
            para j en vértices:      // destino
                si dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    sig[i][j] = sig[i][k]   // reconstrucción

    // Hay ciclo negativo si dist[v][v] < 0 para algún v

El invariante es que, tras la iteración para k, dist[i][j] es el camino más corto de i a j usando solo vértices de los k primeros como intermedios. k tiene que ser el más externo para que eso se cumpla: es lo que amplía de uno en uno el conjunto de escalas permitidas. Poner k en el bucle interno termina igualmente y produce números plausibles, que es justo lo que hace tan difícil de detectar el fallo.

Ejemplo resuelto, paso a paso

Ejecuta Floyd-Warshall sobre un pequeño grafo dirigido y observa cómo una entrada mejora dos veces conforme crece el conjunto de intermedios permitidos.

Grafo de ejemplo: Aristas dirigidas A a B (3), A a C (8), B a C (2), B a D (7) y C a D (1).

1. Inicializar. Solo aristas directas. Desde A: B vale 3, C vale 8, D es inalcanzable. Desde B: C vale 2, D vale 7. Desde C: D vale 1. Toda la diagonal vale 0.
2. k = A. No cambia nada. Ninguna arista apunta hacia A, así que dist[i][A] es infinito para todo i distinto y ningún camino puede pasar por A.
3. k = B. Dos mejoras. dist[A][C] baja de 8 a dist[A][B] + dist[B][C] = 3 + 2 = 5. dist[A][D] pasa de infinito a 3 + 7 = 10, la primera ruta finita de A a D.
4. k = C. Dos más. dist[A][D] vuelve a mejorar, de 10 a dist[A][C] + dist[C][D] = 5 + 1 = 6, y fíjate en que usa el valor de dist[A][C] que la pasada k = B acaba de mejorar. dist[B][D] baja de 7 a 2 + 1 = 3.
5. k = D. No cambia nada, ya que D no tiene aristas salientes y no puede servir de intermedio.

Las distancias finales desde A son B 3, C 5, D 6. La entrada A a D mejoró dos veces, de infinito a 10 y luego a 6, lo que muestra la estratificación de forma directa: la pasada k = C solo pudo encontrar la ruta mejor porque la pasada k = B ya había mejorado A a C. Esa dependencia es la razón de que k deba ser el bucle externo.

Complejidad y de dónde sale

Tiempo: O(V^3) · Espacio: O(V^2)

Tres bucles anidados sobre todos los vértices dan exactamente V al cubo iteraciones, cada una con trabajo constante. No hay salida anticipada ni dependencia del número de aristas, así que el algoritmo cuesta lo mismo en un grafo disperso que en uno denso. El espacio es la matriz V por V de distancias, más una segunda matriz si quieres reconstruir los caminos y no solo sus longitudes. En la práctica V al cubo es aceptable hasta unos pocos miles de vértices; con 5.000 son 125.000 millones de operaciones, y ejecutar Dijkstra desde cada vértice, en O(V·E·log V), pasa a ser mejor opción en grafos dispersos.

Cuándo usar Algoritmo de Floyd-Warshall y cuándo no

Floyd-Warshall gana en densidad y simplicidad, y pierde con claridad en grafos dispersos grandes.

Errores frecuentes

• Poner el bucle k en cualquier sitio que no sea el más externo. Este es el fallo que define a Floyd-Warshall. Con k en el interior el invariante se rompe y el resultado queda silenciosamente demasiado grande para algunos pares. No produce ningún error y parece razonable, así que sobrevive a las pruebas superficiales. El orden debe ser k, luego i, luego j.
• Sumar sobre infinito. Si el infinito se representa como un entero grande, dist[i][k] + dist[k][j] desborda y da la vuelta a un número negativo, creando caminos mínimos inexistentes. Protege la suma, o usa un centinela lo bastante pequeño como para que duplicarlo no desborde.
• Ejecutarlo sobre un grafo con ciclo negativo sin comprobarlo. El algoritmo no falla, simplemente devuelve valores sin sentido. Tras los bucles, cualquier vértice con dist[v][v] por debajo de cero está en un ciclo negativo. Compruébalo antes de fiarte de la matriz.
• Usarlo en un grafo disperso grande. V al cubo ignora E por completo. En un grafo con 10.000 vértices y 30.000 aristas, Floyd-Warshall hace un billón de operaciones mientras que Dijkstra desde cada vértice hace unos cientos de millones.
• Olvidar inicializar la diagonal. dist[v][v] debe empezar en 0, no en infinito. Dejarla infinita rompe las primerísimas relajaciones y corrompe en silencio todo lo que viene después.

Preguntas frecuentes

¿Para qué sirve el algoritmo de Floyd-Warshall?

Calcula los caminos mínimos entre todos los pares de vértices de un grafo con pesos en una sola ejecución. Se usa para tablas de distancias entre todos los pares en planificación de rutas, para calcular la clausura transitiva de una relación, para hallar el diámetro de un grafo, para detectar arbitraje entre todos los pares de divisas a la vez, y en general cuando vas a consultar muchos pares origen-destino distintos.

¿Cuál es la complejidad temporal de Floyd-Warshall?

O(V al cubo) en tiempo y O(V al cuadrado) en espacio, sin dependencia alguna del número de aristas. Tres bucles anidados recorren todos los vértices con trabajo constante en el interior y no hay terminación anticipada. Eso lo hace insensible a la densidad, lo que es una ventaja en grafos densos y un serio inconveniente en los dispersos.

¿Por qué k debe ser el bucle más externo?

Porque k representa el conjunto de vértices permitidos como intermedios, y el algoritmo hace crecer ese conjunto de uno en uno. Tras la pasada de un k dado, cada entrada es correcta usando solo los k primeros vértices como escalas. Si k no es el más externo ese invariante nunca se cumple, y el algoritmo devuelve distancias demasiado grandes sin dar ningún error.

¿Puede Floyd-Warshall manejar pesos negativos?

Sí, las aristas negativas no dan problema mientras no haya ciclo negativo. Al terminar, un valor negativo en la diagonal, es decir dist[v][v] por debajo de cero, significa que v está en un ciclo negativo y que las distancias que lo involucran carecen de sentido.

¿Cuándo debo usar Dijkstra en lugar de Floyd-Warshall?

Cuando el grafo es disperso y los pesos son no negativos. Ejecutar Dijkstra desde cada vértice cuesta O(V·E·log V), que en un grafo con muchas menos de V al cuadrado aristas es drásticamente más rápido que V al cubo. Floyd-Warshall gana en grafos densos, en grafos pequeños y cuando quieres la implementación más corta posible.