Definitivo
En la cola
Aristas revisadas

  • Actual
  • En la cola
  • Definitivo
  • Camino
Un clic en un nodo fija

Más sobre el algoritmo de Dijkstra

Algoritmo de Dijkstra

El algoritmo de Dijkstra encuentra la ruta más corta desde un origen hasta cada uno de los demás nodos cuando las aristas tienen longitudes, como las carreteras entre pueblos. Crece hacia fuera desde el origen, tomando siempre el nodo más cercano que aún no ha terminado. Haz clic en un nodo para empezar desde él, elige un destino si quieres y avanza paso a paso para ver la cola, cómo baja cada distancia al aparecer caminos más cortos y cómo surge el camino más corto. 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. Haz clic en un nodo para que sea el origen; cambia el clic a Destino y haz clic en otro nodo para buscar un camino más corto hasta él. El número de cada arista es su longitud, el de cada nodo su distancia más corta hasta ahora, y la fila bajo el grafo es la cola, primero el más cercano. 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. Haz clic en un nodo para que sea el origen. Para buscar un camino, cambia el clic a Destino y haz clic en otro nodo.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Observa la cola bajo el grafo y la distancia de cada nodo. Nuevo grafo crea otro grafo para probar.

Cómo funciona el algoritmo de Dijkstra

Da al origen la distancia 0 y a todos los demás nodos infinito, y pon el origen en una cola. Después repite: toma el nodo de la cola con la menor distancia y marca esa distancia como definitiva. Para cada vecino suyo que no sea definitivo, suma la longitud de la arista a la distancia del nodo. Si la suma es menor que la distancia que tenía el vecino, pasa a ser su nueva distancia, el nodo se recuerda como el camino hasta él y el vecino entra en la cola si no estaba. Cuando la cola está vacía, cada nodo alcanzable tiene su distancia más corta.

Por qué el nodo más cercano es definitivo

Cuando un nodo es el más cercano de la cola, cualquier otro camino hasta él debe salir de la parte terminada del grafo por algún nodo de la cola, que está al menos igual de lejos, y luego sumar aristas que no pueden ser negativas. Así que ningún otro camino puede ser más corto. Por eso un destino solo es seguro cuando sale de la cola, no cuando se alcanza por primera vez, y por eso el algoritmo de Dijkstra falla con aristas negativas: ahí hace falta el algoritmo de Bellman–Ford. Cuando todas las aristas tienen longitud 1, el algoritmo de Dijkstra hace lo mismo que la búsqueda en anchura.

Preguntas frecuentes

¿Qué es el algoritmo de Dijkstra?

Una forma de encontrar los caminos más cortos desde un nodo de origen hasta todos los demás nodos de un grafo cuyas aristas tienen longitudes de cero o más. Toma una y otra vez el nodo sin terminar más cercano, hace definitiva su distancia y usa sus aristas para acortar las distancias de sus vecinos.

¿Por qué el algoritmo de Dijkstra no funciona con aristas negativas?

Hace definitiva la distancia de un nodo en cuanto ese nodo es el más cercano de la cola. Una arista negativa encontrada después aún podría volver a ese nodo por un camino más corto, así que la distancia definitiva podría ser errónea. El algoritmo de Bellman–Ford admite aristas negativas, siempre que no haya un ciclo con total negativo.

¿Qué diferencia hay entre Dijkstra y BFS?

La búsqueda en anchura cuenta aristas y usa una cola simple. El algoritmo de Dijkstra suma longitudes de aristas y usa una cola de prioridad que siempre da el nodo más cercano. Si todas las aristas tienen longitud 1, ambos encuentran las mismas distancias.

¿Es rápido el algoritmo de Dijkstra?

Con un montículo binario como cola de prioridad, el trabajo crece con (V + E) log V para V nodos y E aristas. Con un montículo de Fibonacci es E + V log V. La aplicación guarda la cola como una lista ordenada, fácil de mostrar y suficiente para grafos pequeños.

¿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