Escala
Pares acortados
Pares revisados

  • Escala actual
  • Ya fue escala
  • Par acortado
  • Camino
Un clic en un nodo fija

Más sobre el algoritmo de Floyd–Warshall

Algoritmo de Floyd–Warshall

¿Qué distancia hay de cada ciudad a todas las demás? Floyd–Warshall lo responde de una vez, con una tabla y tres bucles anidados. Cada ronda admite un nodo más como escala y pregunta, para cada par, si el desvío por él es más corto. Avanza paso a paso para ver cómo se llena la tabla y bajan las distancias. Pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. La tabla contiene la distancia más corta encontrada hasta ahora entre cada par de nodos; el número de cada arista es su longitud. Cada ronda admite un nodo más como escala en el camino, y cada paso muestra un par que se acorta pasando por él. Haz clic en un nodo para que sea el origen; cambia el clic a Destino y haz clic en otro nodo para ver al final el camino más corto entre ellos. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
  2. Observa la tabla: la fila y la columna de la escala actual están coloreadas, y cada paso escribe una distancia más corta.
  3. Elige un origen y un destino para ver al final el camino más corto entre ellos. Nuevo grafo crea otro grafo para probar.

Cómo funciona Floyd–Warshall

Haz una tabla con una fila y una columna por nodo. Escribe 0 en la diagonal, la longitud de la arista donde dos nodos están unidos e infinito en todo lo demás. Luego toma cada nodo k por turno como posible escala. Para cada par i, j, compara la distancia de i a j en la tabla con la distancia de i a k más la distancia de k a j, y quédate con la menor. Tras el último nodo, cada casilla es la distancia más corta entre sus dos nodos.

Por qué funciona

Tras la ronda de k, la tabla contiene, para cada par, el camino más corto cuyas escalas están todas entre los nodos tratados hasta ahora. La ronda del siguiente nodo solo tiene que decidir si ese nodo ayuda: un camino más corto que pasa por él es un camino más corto hasta él más un camino más corto desde él, y ambos ya están en la tabla. Esta forma de construir una respuesta grande a partir de otras más pequeñas ya encontradas se llama programación dinámica. Con aristas negativas sigue funcionando, y un número negativo en la diagonal revela un ciclo negativo.

Preguntas frecuentes

¿Qué es el algoritmo de Floyd–Warshall?

Un algoritmo que encuentra la distancia más corta entre cada par de nodos de un grafo ponderado. Mantiene una tabla de distancias y, para cada nodo por turno, comprueba si pasar por ese nodo acorta algún par.

¿Es rápido Floyd–Warshall?

Tiene tres bucles anidados sobre los n nodos, así que el trabajo crece con n³, y la tabla necesita n² casillas. Eso va bien para grafos de unos cientos de nodos. Para grafos grandes y dispersos, ejecutar el algoritmo de Dijkstra desde cada nodo es más rápido.

¿Admite Floyd–Warshall aristas negativas?

Sí, siempre que no haya un ciclo negativo. Si lo hay, alguna casilla de la diagonal se vuelve negativa, y así es como Floyd–Warshall lo detecta.

¿Cómo obtengo los caminos, no solo las distancias?

Guarda una segunda tabla con el siguiente nodo en el camino de i a j. Cada vez que un par se acorta pasando por k, copia el siguiente nodo de i hacia k. Siguiendo esa tabla de i a j se obtiene el camino.

¿Se envía mi grafo a algún sitio?

No. El grafo se crea y la tabla se llena en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor