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.