Floyd-Warshall: caminos más cortos entre todos los pares

De qué trata este capítulo

Tanto Dijkstra como Bellman-Ford responden "caminos más cortos desde un origen". A veces necesitas todos — la distancia mínima entre cada par de nodos: una tabla completa de distancias para una red de carreteras, la alcanzabilidad transitiva de un grafo de dependencias, la cota más ajustada entre cada par de variables de un sistema de restricciones. Floyd-Warshall calcula esa matriz V×V completa con uno de los fragmentos de código más cortos, más raros y más elegantes de este libro — un triple ciclo anidado cuyo cuerpo es una sola línea. Maneja aristas negativas como Bellman-Ford, detecta ciclos negativos con solo mirar su propia diagonal, y su acceso a memoria denso y regular hace que corra casi a velocidad de hardware a pesar de su costo $O(V^3)$. En este capítulo lo construimos, vemos cómo se llena la matriz de distancias un nodo intermedio a la vez, y medimos en qué punto su enfoque bruto de todo-de-un-jalón le gana a la alternativa de correr Dijkstra desde cada nodo.

Un poco de historia

El algoritmo lleva el nombre de Robert Floyd, quien lo publicó en 1962, y de Stephen Warshall, quien publicó esencialmente la misma idea ese mismo año para calcular la cerradura transitiva de una relación — si cada nodo puede alcanzar a los demás, la versión booleana del problema del camino más corto. Bernard Roy ya lo había descrito desde 1959, así que de vez en cuando se le llama algoritmo de Roy-Floyd-Warshall. La aportación de Warshall fue la idea clave que sobrevive en la estructura del ciclo: para saber si $i$ puede alcanzar a $j$, considera los nodos intermedios uno por uno, y permitir un punto de paso más solo puede agregar alcanzabilidad. Floyd llevó la misma idea a caminos más cortos con pesos cambiando "o" por "min" y "y" por "más". Esa correspondencia — la alcanzabilidad son caminos más cortos sobre el semianillo booleano, y los caminos más cortos son alcanzabilidad sobre el semianillo min-plus — es la razón de que las mismas tres líneas resuelvan ambos problemas, y es un ejemplo chiquito y hermoso de cómo un mismo esqueleto de algoritmo se generaliza entre problemas con solo cambiarle la aritmética.

La intuición

Aquí va la idea de programación dinámica, y es lo bastante sutil como para valer la pena enunciarla con cuidado. Numera los nodos de 0 a V−1. Define el subproblema: ¿cuál es la distancia más corta de $i$ a $j$ si el camino solo puede pasar por nodos intermedios tomados de $\{0, 1, \dots, k-1\}$? Llámala $D_k[i][j]$. Cuando $k = 0$ no se permite ningún intermedio, así que $D_0[i][j]$ es simplemente la arista directa (o infinito). Ahora haz crecer $k$ en uno — permite también el nodo $k$ como punto de paso. Para cada par $(i, j)$, o el mejor camino sigue sin usar $k$ (queda el valor viejo), o sí lo usa, y en ese caso va $i \rightsquigarrow k \rightsquigarrow j$ usando solo intermedios anteriores en cada mitad, o sea $D_k[i][k] + D_k[k][j]$. Entonces la actualización es $D_{k+1}[i][j] = \min(D_k[i][j],\ D_k[i][k] + D_k[k][j])$. Después de permitir cada nodo como intermedio, la restricción desaparece y te quedas con las distancias más cortas reales.

Lo asombroso es que no necesitas guardar una matriz por cada $k$ — puedes actualizar la única matriz in place, siempre y cuando el ciclo sobre $k$ sea el más externo. Ese orden garantiza que cuando lees $dist[i][k]$ y $dist[k][j]$, esos valores ya reflejan todos los intermedios por debajo de $k$, que es justo lo que necesita la recurrencia. Si te equivocas en el orden de los ciclos — si metes $k$ adentro — el algoritmo calcula basura en silencio. Todo son tres líneas, y cada sutileza vive en el hecho de que $k$ va primero.

Complejidad: cómo escala

Tres ciclos anidados sobre V nodos dan tiempo $O(V^3)$ y espacio $O(V^2)$ para la matriz. Eso es fijo sin importar cuántas aristas tenga el grafo — Floyd-Warshall toca cada celda de la matriz por cada nodo intermedio, ya sea que el grafo esté casi vacío o completo. La alternativa para todos los pares es correr un algoritmo de un solo origen desde cada uno de los V nodos: Dijkstra desde cada origen es $O(V \cdot (V+E)\log V)$, que sale más barato en grafos dispersos pero crece con la cantidad de aristas. Así que quién gana depende de la densidad, y de eso trata el duelo — la misma respuesta de todos los pares, calculada de las dos formas, conforme el grafo se hace más denso:

Fíjate en las formas, no nada más en las alturas. La línea de Floyd-Warshall es prácticamente plana — a su costo le da igual cuántas aristas existan, porque siempre procesa la matriz completa. La de Dijkstra-desde-cada-nodo sube constantemente conforme se acumulan aristas, porque cada corrida de Dijkstra hace más trabajo en un grafo más denso. En un grafo disperso (grado de salida promedio 2) correr Dijkstra V veces fue como cinco veces más rápido; para grado de salida 80 esa ventaja se había reducido a 1.4×, y las líneas van convergiendo. En un lenguaje compilado el cruce sí llega — el ciclo interno de Floyd-Warshall, apretado, sin ramas y amigable con el cache, rebasa a las operaciones de heap llenas de saltos de punteros de Dijkstra en grafos densos. Aquí en Python puro el overhead por operación del intérprete mantiene atrás al triple ciclo simple, pero la tendencia es la lección de verdad: el precio de Floyd-Warshall es ciego a la densidad, así que entre más denso el grafo, más rinde su simplicidad bruta.

En qué es bueno y en qué no

Floyd-Warshall brilla cuando de verdad necesitas distancias entre todos los pares y el grafo es chico o denso: unos cuantos cientos de nodos, o un grafo donde abundan las aristas. Su cuerpo de tres líneas es facilísimo de implementar bien (una vez que le atinas al orden de los ciclos), maneja aristas negativas que si no te obligarían a correr Bellman-Ford por cada origen, y su acceso regular a arrays es amigable con el cache y se vectoriza bien, que es justo por lo que scipy y networkx lo implementan en código compilado. También es la herramienta natural para la cerradura transitiva, para "apretar" una matriz de restricciones hasta sus cotas implícitas, y para cualquier cómputo min-plus / de semianillo sobre todos los pares.

Donde es la elección equivocada es en grafos grandes y dispersos. Su tiempo $O(V^3)$ y, peor aún, su memoria $O(V^2)$ son costos fijos: una red de carreteras de un millón de nodos necesitaría una matriz de un billón de entradas, lo cual es absurdo, mientras que Dijkstra desde un solo origen corre en tiempo casi lineal y solo toca los nodos alcanzables. Para consultas de un solo origen es puro desperdicio — calcularías la matriz entera para leer un renglón. Y en problemas de todos los pares sobre grafos dispersos, correr Dijkstra (o Bellman-Ford, para pesos negativos, vía el algoritmo de Johnson) desde cada nodo es asintóticamente mejor. Floyd-Warshall es un especialista en grafos chicos y densos, no una herramienta general de caminos más cortos.

Los datos, o las entradas

El duelo corre sobre grafos dirigidos aleatorios de 140 nodos con densidad creciente y cronometra el cálculo completo de todos los pares de dos formas: el triple ciclo de Floyd-Warshall contra correr Dijkstra desde cada nodo. La corrección se verifica de tres maneras independientes — contra Dijkstra-desde-cada-nodo en grafos no negativos, contra Bellman-Ford-desde-cada-nodo en grafos con aristas negativas, y confirmando que las aristas de cada camino reconstruido sumen su distancia en la matriz — además de ciclos negativos sembrados a propósito para confirmar la detección por la diagonal. La animación corre sobre un grafo chiquito de seis nodos y muestra la matriz de distancias misma: cada celda es una distancia (∞ donde todavía no hay camino), y ves cómo las celdas mejoran conforme se enciende cada nuevo nodo intermedio.

Constrúyelo, una función a la vez

El algoritmo completo — inicializa con las aristas directas y luego el triple ciclo:

def floyd_warshall(n, edges):
    """All-pairs shortest distances. `edges` is a list of (u, v, w), any sign. Build the
    matrix of direct edges, then for each intermediate node k, ask of every pair (i, j)
    whether going i → k → j beats the best i → j found so far. After all k, the matrix holds
    every shortest distance. O(V^3) time, O(V^2) space. The order of the loops matters: k
    MUST be outermost, so that when we use dist[i][k] and dist[k][j] they already account for
    intermediates < k."""
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w                   # keep the cheapest parallel edge
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                     # i can't reach k, so k is no help from i
            di = dist[i]
            for j in range(n):
                through_k = dik + dk[j]
                if through_k < di[j]:
                    di[j] = through_k        # routing i → k → j is cheaper
    return dist

El mismo ciclo pero guardando una matriz de siguiente salto, para poder reconstruir cualquier camino más corto:

def floyd_warshall_paths(n, edges):
    """Same algorithm, but remember a next-hop matrix so any shortest path can be rebuilt.
    nxt[i][j] is the first node to step to when going from i toward j."""
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        nxt[i][i] = i
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]     # first step toward k is the first step toward j
    return dist, nxt


def reconstruct(nxt, i, j):
    """Walk the next-hop matrix to list the actual shortest path i → j (or None if none)."""
    if nxt[i][j] is None:
        return None
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path

Y la detección de ciclos negativos, directo de la diagonal:

def has_negative_cycle(dist):
    """After Floyd-Warshall, a node reachable more cheaply than 0 *from itself* sits on a
    negative cycle — going around the loop lowered its own distance below zero."""
    return any(dist[i][i] < 0 for i in range(len(dist)))

Míralo funcionar

Aquí está la matriz de distancias de un grafo de seis nodos mientras corre Floyd-Warshall. Cada celda $(i, j)$ guarda la mejor distancia actual de $i$ a $j$; la diagonal en verde azulado es la distancia cero de un nodo a sí mismo, y las celdas oscuras son ∞ — todavía no se conoce camino. El primer cuadro son solo las aristas directas. Después, cuadro por cuadro, vamos encendiendo cada nodo como intermedio permitido: las celdas que mejoran destellan en naranja. Fíjate cómo permitir el nodo 1 como punto de paso llena $0 \to 2$ (vía $0 \to 1 \to 2$), y cómo los intermedios posteriores van acomodando rutas más largas. Para el último cuadro la matriz tiene todas las distancias más cortas — la respuesta completa de todos los pares, armada un punto de paso a la vez:

El código completo

La pestaña "desde cero" es Floyd-Warshall con reconstrucción de caminos y detección de ciclos; la pestaña de librería es la estrategia de Dijkstra-desde-cada-nodo contra la que compitió (y con la que se verificó), con las llamadas de networkx y scipy que realmente usarías anotadas hasta arriba. Cambia entre ellas.

"""Floyd-Warshall — the shortest distance between EVERY pair of nodes, all at once, in a
strikingly short triple loop. Where Dijkstra and Bellman-Ford answer "shortest paths from
one source," Floyd-Warshall fills the whole V×V distance matrix. It handles negative edges
like Bellman-Ford, detects negative cycles (a node ends up cheaper than zero from itself),
and its inner loop is so simple and regular it runs close to hardware speed.

The idea is dynamic programming over an unusual dimension: not "paths of at most k edges"
(that was Bellman-Ford) but "paths allowed to route through only the first k nodes as
intermediates." Start with direct edges only (no intermediates). Then permit node 0 as a
waypoint and relax; then also node 1; and so on. After every node has been allowed as an
intermediate, dist[i][j] is the true shortest distance. That's the entire algorithm:

    for k: for i: for j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
"""

INF = float("inf")


# region: floyd_warshall
def floyd_warshall(n, edges):
    """All-pairs shortest distances. `edges` is a list of (u, v, w), any sign. Build the
    matrix of direct edges, then for each intermediate node k, ask of every pair (i, j)
    whether going i → k → j beats the best i → j found so far. After all k, the matrix holds
    every shortest distance. O(V^3) time, O(V^2) space. The order of the loops matters: k
    MUST be outermost, so that when we use dist[i][k] and dist[k][j] they already account for
    intermediates < k."""
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w                   # keep the cheapest parallel edge
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                     # i can't reach k, so k is no help from i
            di = dist[i]
            for j in range(n):
                through_k = dik + dk[j]
                if through_k < di[j]:
                    di[j] = through_k        # routing i → k → j is cheaper
    return dist
# endregion


# region: with_paths
def floyd_warshall_paths(n, edges):
    """Same algorithm, but remember a next-hop matrix so any shortest path can be rebuilt.
    nxt[i][j] is the first node to step to when going from i toward j."""
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        nxt[i][i] = i
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]     # first step toward k is the first step toward j
    return dist, nxt


def reconstruct(nxt, i, j):
    """Walk the next-hop matrix to list the actual shortest path i → j (or None if none)."""
    if nxt[i][j] is None:
        return None
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path
# endregion


# region: negative_cycle
def has_negative_cycle(dist):
    """After Floyd-Warshall, a node reachable more cheaply than 0 *from itself* sits on a
    negative cycle — going around the loop lowered its own distance below zero."""
    return any(dist[i][i] < 0 for i in range(len(dist)))
# endregion

"""The library counterpart and the contrast. In production, all-pairs shortest paths come
from networkx (`nx.floyd_warshall_numpy`) or scipy (`scipy.sparse.csgraph.shortest_path`),
both of which drop into compiled/vectorized code for the O(V^3) work:

    import networkx as nx
    D = nx.floyd_warshall_numpy(G, weight="weight")   # a V×V distance matrix

The instructive comparison, though, is against the ALTERNATIVE strategy for all-pairs on
non-negative graphs: run Dijkstra from every source. That's O(V·(V+E) log V), which beats
Floyd-Warshall's O(V^3) on sparse graphs but loses on dense ones — the trade the face-off
measures. `all_pairs_dijkstra` below is that strategy, and also the trusted reference the
trace generator checks Floyd-Warshall against on non-negative graphs.
"""
import heapq

INF = float("inf")


# region: all_pairs_dijkstra
def dijkstra(adj, start, n):
    dist = [INF] * n
    dist[start] = 0
    settled = [False] * n
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if settled[u]:
            continue
        settled[u] = True
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist


def all_pairs_dijkstra(n, edges):
    """Run Dijkstra from every node → the full distance matrix, in O(V·(V+E) log V). Correct
    only for non-negative weights (Dijkstra's requirement), and the strategy Floyd-Warshall
    competes with on such graphs."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    return [dijkstra(adj, s, n) for s in range(n)]
# endregion

Desde cero vs librería

Aquí la comparación no es de corrección — Floyd-Warshall y Dijkstra-desde-cada-nodo coinciden exactamente en grafos no negativos, como lo confirman las verificaciones. Es una decisión de estrategia para la misma meta de todos los pares, y depende de la forma del grafo. Floyd-Warshall hace una cantidad fija de trabajo denso y regular, $O(V^3)$, sin importar las aristas; Dijkstra-por-nodo hace menos trabajo cuando las aristas escasean y más cuando abundan. Así que la respuesta honesta a "cuál algoritmo de todos los pares" es "depende de la densidad y del tamaño", y la gráfica muestra exactamente ese intercambio: una línea plana contra una que sube. Esta es una forma que se repite en este libro — metas asintóticamente idénticas con constantes distintas y sensibilidades distintas, donde la elección correcta depende del régimen en el que estés. En producción usarías el Floyd-Warshall compilado de scipy o de networkx en grafos chicos y densos, y Dijkstra-por-nodo (o el de Johnson, si hay negativos) en los grandes y dispersos; construir el triple ciclo una vez es lo que vuelve concretos —en lugar de memorizados— la sutileza del orden de los ciclos y el intercambio de densidad.

Dónde te lo vas a encontrar

Floyd-Warshall corre donde sea que se necesite una respuesta de todos los pares chica y densa. Las herramientas de análisis de redes lo calculan para obtener las latencias entre cada par y para derivar métricas como el diámetro de un grafo y la centralidad de intermediación. Es el método clásico para la cerradura transitiva de una relación — alcanzabilidad en grafos de dependencias, retículas de subtipado, optimización de consultas de bases de datos. Los compiladores y los analizadores estáticos usan su forma min-plus para apretar sistemas de restricciones de diferencia y para calcular resúmenes interprocedurales. Aparece en las construcciones de expresión regular a autómata (el algoritmo de Kleene es el mismo ciclo sobre otro semianillo), en el precálculo de tablas de ruteo para redes chicas, y por toda la investigación de operaciones donde sea que se quiera una matriz de costos entre todos los pares. Siempre que el grafo sea lo bastante chico como para que quepa una matriz $V^2$ y quieras cada distancia, esas tres líneas de Floyd-Warshall son la herramienta.

Puntos clave

Floyd-Warshall calcula las distancias más cortas entre todos los pares con programación dinámica sobre qué nodos se permiten como intermedios — haz crecer el conjunto permitido un nodo a la vez, actualizando in place con $k$ como ciclo más externo — en tiempo $O(V^3)$ y espacio $O(V^2)$. Maneja aristas negativas y detecta ciclos negativos desde su propia diagonal, y el mismo esqueleto de tres líneas calcula la cerradura transitiva cambiando min/plus por or/and. Su costo es independiente de la cantidad de aristas, así que es el especialista para problemas de todos los pares en grafos chicos o densos, y la herramienta equivocada para grafos grandes y dispersos, donde Dijkstra por nodo gana tanto en tiempo como en memoria.

Con Floyd-Warshall se cierra el hilo de caminos más cortos de este nivel: sin pesos (BFS), un solo origen no negativo (Dijkstra), un solo origen con negativos (Bellman-Ford), todos los pares (Floyd-Warshall). El siguiente capítulo, A*, regresa a un solo origen pero agrega una idea nueva: una heurística que estima la distancia que falta hasta una meta específica, guiando la búsqueda para que explore muchos menos nodos que Dijkstra cuando ya sabes a dónde vas.