Algoritmo de Floyd‑Warshall: Guía Completa con Ejemplos en Python

Introducción

El algoritmo de Floyd‑Warshall es una técnica clásica de programación dinámica que permite calcular la distancia mínima entre todos los pares de vértices de un grafo ponderado. A diferencia de algoritmos como Dijkstra, que resuelven el problema para un único origen, Floyd‑Warshall trabaja de forma global y es capaz de manejar aristas con pesos negativos (siempre que no existan ciclos negativos).

Fundamentos matemáticos

Sea V el conjunto de vértices y W[i][j] el peso de la arista que conecta i con j. La idea central es actualizar iterativamente una matriz de distancias D de la forma:

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

para cada vértice intermedio k. Al final del proceso, D[i][j] contiene la longitud del camino más corto entre i y j.

Complejidad temporal y espacial

El algoritmo recorre tres bucles anidados de tamaño n = |V|:

• Tiempo: O(n³). Adecuado para grafos con pocas decenas de miles de vértices, pero no para grafos masivos.
• Espacio: O(n²) para almacenar la matriz de distancias y, opcionalmente, la matriz de predecesores.

En entornos con GPUs o CPUs con muchos núcleos, la triple iteración se presta a paralelismo mediante vectorización o OpenMP.

Implementación paso a paso en Python

A continuación se muestra una versión idiomática y optimizada del algoritmo, con soporte para detección de ciclos negativos.

import sys
from typing import List, Tuple

def floyd_warshall(weight: List[List[float]]) -> Tuple[List[List[float]], List[List[int]]]:
    """Calcula todas las distancias mínimas y la matriz de predecesores.

    Args:
        weight: Matriz n x n con los pesos. Use float('inf') para aristas inexistentes.
    Returns:
        dist: Matriz de distancias mínimas.
        pred: Matriz de predecesores para reconstruir caminos.
    """
    n = len(weight)
    # Copia la matriz para no mutar la original
    dist = [row[:] for row in weight]
    pred = [[-1 if i == j or weight[i][j] == float('inf') else i for j in range(n)] for i in range(n)]

    for k in range(n):
        # Optimización: almacenar la fila k y columna k en variables locales
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == float('inf'):
                continue
            di = dist[i]
            for j in range(n):
                # Evita cálculos innecesarios cuando dk[j] es infinito
                if dk[j] == float('inf'):
                    continue
                new_dist = dik + dk[j]
                if new_dist < di[j]:
                    di[j] = new_dist
                    pred[i][j] = pred[k][j]

    # Detección de ciclos negativos
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError('Ciclo negativo detectado en el vértice {}'.format(i))

    return dist, pred

def reconstruct_path(pred: List[List[int]], start: int, end: int) -> List[int]:
    """Reconstruye el camino más corto entre start y end usando la matriz de predecesores."""
    if pred[start][end] == -1:
        return []
    path = [end]
    while end != start:
        end = pred[start][end]
        path.append(end)
    path.reverse()
    return path

# -------------------------------------------------------------------
# Ejemplo de uso
INF = float('inf')
graph = [
    [0,   3, INF,   7],
    [8,   0,   2, INF],
    [5, INF,   0,   1],
    [2, INF, INF,   0]
]

if __name__ == '__main__':
    dist, pred = floyd_warshall(graph)
    print('Matriz de distancias mínimas:')
    for row in dist:
        print(row)
    print('\nCamino más corto de 0 a 3:', reconstruct_path(pred, 0, 3))

El bloque anterior incluye:

• Gestión de inf para aristas inexistentes.
• Detección de ciclos negativos y lanzamiento de excepción.
• Función auxiliar reconstruct_path para obtener la secuencia de vértices.

Comparativa con algoritmos alternativos

Otro candidato es el algoritmo de Johnson, que combina re‑pesado con Dijkstra para obtener O(V·E log V) y soporta pesos negativos sin ciclos.

Casos de uso del mundo real

• Ruteo en redes de telecomunicaciones: cálculo de latencias mínimas entre todos los nodos de un backbone.
• Análisis de rutas en videojuegos: generación de tablas de distancia precomputadas para IA.
• Optimización de flujos logísticos: determinar tiempos de tránsito entre almacenes y centros de distribución.

Mejores prácticas y optimizaciones

1. Uso de estructuras vectorizadas: con numpy se pueden reemplazar los bucles por operaciones de broadcasting, reduciendo el factor constante.
2. Paralelismo con multiprocessing o numba: cada iteración k es independiente y puede ejecutarse en varios procesos/threads.
3. Memoria compartida en GPUs: bibliotecas como cupy permiten que la triple iteración se ejecute en la GPU con O(n³) pero a gran velocidad.
4. Detección temprana de ciclos negativos: romper el algoritmo tan pronto como dist[i][i] < 0 para evitar cálculos innecesarios.

Solución de problemas comunes (troubleshooting)

Seguridad y validación de datos

Al consumir grafos provenientes de fuentes externas (APIs, archivos CSV, bases de datos), es fundamental:

• Validar que los pesos sean numéricos y que no haya valores NaN.
• Escapar o sanitizar cualquier entrada que pueda generar inf inesperado.
• Implementar pruebas unitarias que cubran casos con pesos negativos, aristas ausentes y ciclos.

Conclusión

Floyd‑Warshall sigue siendo la herramienta de referencia cuando se necesita una tabla completa de distancias mínimas entre todos los nodos, especialmente en entornos donde los pesos pueden ser negativos y el número de vértices es moderado. Con las optimizaciones modernas (NumPy, Numba, paralelismo) y una adecuada gestión de errores, el algoritmo se mantiene competitivo y fácil de integrar en pipelines de Data Science y DevOps.