Menú principal
Applet | Algoritmo de Dijkstra
Parámetros
Código Python
Visualizador
Cola de prioridad:
Nodo actual:
Parámetros
- En el campo Lista de adyacencias deberás introducir un grafo válido en formato de lista de listas encerradas por [corchetes]. Si imprimes una lista de adyacencias en Python y la pegas aquí ya estará en el formato correcto.
- En los campos Nodo inicial y Nodo objetivo deberás definir el nodo desde el que parte el algoritmo y el nodo que se quiere alcanzar con la mínima distancia.
- El deslizador Velocidad controla la velocidad a la que se ejecuta el algoritmo.
- Los botones de colores permiten iniciar la simulación del algoritmo, pausarla, avanzarla paso a paso y reiniciarla.
Sobre este algoritmo
Nombrado en honor a su inventor, el matemático y científico de la computación Edsger W. Dijkstra, este algoritmo permite obtener fácilmente la distancia mínima desde un vértice hasta cualquier otro de un grafo con pesos positivos.
La implementación más habitual, y la estudiada en la asignatura, hace uso de una cola de prioridad (heapq en Python) para seleccionar de forma eficiente el siguiente vértice con la menor distancia acumulada.
Algoritmo de Dijkstra
Algoritmo de Dijkstra