🗺️ Floyd-Warshall — Caminos Más Cortos Entre Todos los Pares

El deslizador de Vértices (de 5 a 7) establece cuántos nodos tiene el grafo aleatorio, lo que también determina el tamaño de la matriz de distancias y cuántos pivotes recorre el algoritmo. Velocidad (de 0,2 a 4) controla la rapidez con la que Reproducir avanza automáticamente por los pasos de relajación; no tiene efecto cuando se usa Paso, que siempre avanza exactamente las relajaciones de un pivote por clic.

Reproducir ejecuta el algoritmo de forma continua a la Velocidad elegida, avanzando i, j y finalmente el pivote k hasta que se han procesado todos los pivotes y la ejecución se marca como Completada. Paso, en cambio, avanza un pivote k completo en un solo clic, aplicando todas sus relajaciones (i, j) a la vez, lo cual es útil para pausar e inspeccionar la matriz entre pivotes.

Eliges los vértices de Origen y Destino en los selectores desplegables. Una vez finalizada la ejecución, la simulación reconstruye el camino siguiendo la matriz de siguiente salto desde el origen hasta llegar al destino, y dibuja cada arista de esa ruta en morado sobre el grafo, mientras que el dato de distancia del camino muestra el peso total, o el símbolo de infinito si no existe ningún camino.

Un símbolo de infinito significa que aún no se ha encontrado ningún camino entre esa fila y esa columna. La diagonal siempre empieza en 0 porque cada vértice se alcanza a sí mismo con coste cero. A medida que el pivote k avanza en las relajaciones del panel de registro, las entradas de infinito se convierten en números finitos cuando k resulta ser un paso intermedio útil entre dos vértices que no estaban directamente conectados.

Regenerar construye un nuevo grafo dirigido aleatorio: un anillo conectado para que cada vértice pueda alcanzar al siguiente, más un puñado de aristas aleatorias adicionales con pesos de 1 a 9, de modo que la forma del problema cambia en cada ejecución. Cambiar el deslizador de Vértices también desencadena una regeneración completa, ya que el tamaño de la matriz y la longitud del anillo dependen del número de vértices.

Floyd-Warshall calcula el camino más corto entre cada par de vértices de un grafo ponderado a la vez. En lugar de ejecutar un algoritmo de fuente única desde cada nodo, rellena una matriz V×V donde dist[i][j] es la longitud del camino más corto de i a j. Funciona en grafos dirigidos o no dirigidos y admite pesos de arista negativos siempre que no haya un ciclo negativo.

El algoritmo utiliza un triple bucle con un pivote externo k. Para cada par (i, j) comprueba si ir de i a k y luego de k a j es más corto que la mejor opción actual: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Una vez que el pivote ha recorrido todos los vértices, se han encontrado todos los caminos más cortos que usan únicamente vértices intermedios del conjunto completo.

Hay tres bucles anidados, cada uno recorriendo todos los V vértices: el pivote k, el origen i y el destino j. Eso da V × V × V = V³ pasos de relajación, por lo que la complejidad temporal es O(V³). La complejidad espacial es O(V²) para la matriz de distancias, más otro O(V²) si se mantiene una matriz de predecesores para reconstruir el camino.

Tras la iteración k, dist[i][j] contiene el camino más corto de i a j que solo puede pasar por vértices intermedios numerados de 1 a k. Como el pivote k es el bucle más externo, cuando usamos dist[i][k] y dist[k][j] ya tienen en cuenta todos los pivotes anteriores, de modo que la recurrencia siempre se construye sobre subsoluciones óptimas. Este es el invariante clásico de programación dinámica que hace correcto al algoritmo.

A diferencia de Dijkstra, Floyd-Warshall tolera pesos de arista negativos y sigue devolviendo caminos más cortos correctos. Un ciclo negativo, sin embargo, significa que algunos caminos más cortos quedan indefinidos porque se puede dar vueltas indefinidamente para reducir el coste. Se puede detectar un ciclo negativo después de la ejecución: si alguna entrada diagonal dist[i][i] se vuelve negativa, el vértice i está en un ciclo negativo. Esta simulación usa únicamente pesos no negativos para mantener los resultados bien definidos.

Durante la inicialización, una matriz de siguiente salto next[i][j] se fija a j siempre que exista una arista directa. Cada vez que una relajación a través del pivote k mejora dist[i][j], copiamos next[i][j] = next[i][k], registrando que la mejor ruta ahora comienza dirigiéndose hacia k. Para reconstruir el camino se sigue next[i][j] desde el origen hasta llegar al destino, recopilando los vértices por el camino.

Dijkstra resuelve el problema del camino más corto de fuente única y es rápido en grafos dispersos, pero requiere pesos no negativos y solo da caminos desde un único origen. Ejecutar Dijkstra desde cada vértice cuesta aproximadamente O(V·E·log V) con un montículo, lo que supera a Floyd-Warshall en grafos dispersos grandes. Floyd-Warshall, con su coste plano O(V³) y factores constantes pequeños, es más sencillo de programar y a menudo gana en grafos pequeños o densos y cuando realmente se necesitan todos los pares.

Bellman-Ford también es de fuente única pero, al igual que Floyd-Warshall, acepta aristas negativas y puede detectar ciclos negativos. Se ejecuta en O(V·E) por origen. Si necesitas caminos más cortos desde un único origen en un grafo con aristas negativas, Bellman-Ford es la opción natural; si necesitas todos los pares a la vez, los tres bucles compactos de Floyd-Warshall suelen ser más fáciles y competitivos en grafos densos.

Una entrada de ∞ significa que actualmente no se conoce ningún camino entre esos dos vértices. La diagonal dist[i][i] empieza en 0 porque la distancia de un vértice a sí mismo es cero. A medida que avanza el pivote, las entradas ∞ pueden volverse finitas cuando un vértice intermedio conecta dos nodos previamente desconectados, que es exactamente el 'ajuste' de la matriz que se ve en la animación.

Se utiliza para tablas de enrutamiento en redes pequeñas, calcular el cierre transitivo de una relación, encontrar el diámetro y la centralidad de un grafo, y resolver consultas de distancia entre todos los pares en mapas, juegos e investigación operativa. Una variante booleana calcula alcanzabilidad, y una variante max-min resuelve problemas de camino más ancho o de cuello de botella intercambiando las operaciones min/suma por max/min.