- Actual
- Tiene distancia
- Arista usada
- Camino
- Ciclo negativo
Algoritmo de Bellman–Ford
El algoritmo de Dijkstra falla cuando una arista tiene longitud negativa, como una carretera que te paga un peaje en vez de cobrártelo. El algoritmo de Bellman–Ford no: simplemente revisa cada arista una y otra vez hasta que nada mejora, e incluso sabe decir cuándo un ciclo hace que las distancias bajen sin fin. Haz clic en un nodo para empezar desde él y avanza pasada a pasada. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Cada arista es de un solo sentido, como indica su flecha, y el número que lleva es su longitud, que puede ser negativa. 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 hasta él. El número de cada nodo es su distancia hasta ahora. Marca Añadir un ciclo negativo para ver cómo Bellman–Ford encuentra uno. 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
- Haz clic en un nodo para que sea el origen. Para ver un camino al final, cambia el clic a Destino y haz clic en otro nodo.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
- Marca Añadir un ciclo negativo para ver cómo Bellman–Ford encuentra uno. Nuevo grafo crea otro grafo para probar.
Cómo funciona Bellman–Ford
Da al origen distancia 0 y a todos los demás nodos infinito. Luego haz pasadas: en cada pasada, revisa una vez cada arista u → v. Si u tiene distancia y dist(u) más la longitud de la arista es menor que dist(v), baja dist(v) y recuerda u como el camino hasta allí. Tras la pasada k se conoce cada camino más corto que usa como mucho k aristas. Un camino más corto visita cada nodo como mucho una vez, así que tiene como mucho n − 1 aristas, y siempre bastan n − 1 pasadas. Si una pasada entera no cambia nada, la búsqueda puede parar antes.
Encontrar un ciclo negativo
Si las aristas de un ciclo suman menos de cero, dar otra vuelta siempre acorta un camino, así que no hay ningún camino más corto. Bellman–Ford lo nota: tras n − 1 pasadas, una pasada más no debería cambiar nada. Si una arista aún se puede relajar, desde el origen se llega a un ciclo negativo, y seguir hacia atrás los nodos recordados desde esa arista lleva hasta él. En la aplicación, el ciclo se dibuja en rojo.
Preguntas frecuentes
¿Qué es el algoritmo de Bellman–Ford?
Un algoritmo que encuentra los caminos más cortos desde un origen a todos los demás nodos en un grafo cuyas aristas pueden tener longitudes negativas. Relaja cada arista en pasadas repetidas, y avisa de un ciclo negativo si se puede llegar a uno desde el origen.
¿Por qué falla el algoritmo de Dijkstra con aristas negativas?
Dijkstra hace definitiva la distancia de un nodo en cuanto es el más cercano de la cola. Una arista negativa encontrada después aún puede volver a ese nodo por un camino más corto, así que la distancia definitiva puede ser errónea. Bellman–Ford nunca hace definitiva una distancia antes de tiempo; sigue revisando cada arista.
¿Por qué n − 1 pasadas?
Un camino más corto nunca necesita visitar un nodo dos veces, así que tiene como mucho n − 1 aristas. Cada pasada alarga los caminos más cortos conocidos al menos una arista, así que tras n − 1 pasadas se han encontrado todos.
¿Qué tan rápido es Bellman–Ford?
Cada pasada revisa las E aristas y hay como mucho V − 1 pasadas, así que el trabajo crece con V × E. Es más lento que el algoritmo de Dijkstra, y por eso Bellman–Ford se usa cuando las aristas pueden ser negativas.
¿Se envía mi grafo a algún sitio?
No. El grafo se crea y se recorre 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