¿Conoces el algoritmo de Dijkstra y su importancia?
El algoritmo de Dijkstra es un algoritmo de búsqueda de caminos más cortos en un grafo ponderado, dirigido o no dirigido.
Fue propuesto por el científico de la computación Edsger Dijkstra, en 1956, y ha sido ampliamente utilizado en diversas aplicaciones como, por ejemplo, en sistemas de navegación, enrutamiento de redes y optimización de rutas.
También tiene aplicación en la planificación de proyectos, con el propósito de determinar la secuencia óptima de actividades en un proyecto, minimizando el tiempo requerido para completar el proyecto y optimizando el uso de recursos.
El objetivo del algoritmo de Dijkstra es encontrar el camino más corto desde un nodo de origen dado hacia todos los demás nodos del grafo.
El algoritmo de Dijkstra funciona de la siguiente manera:
1. Asigna una distancia inicial de infinito a todos los nodos, excepto al nodo de origen, al cual se le asigna una distancia de 0. También se crea un conjunto vacío llamado “conjunto de nodos visitados”.
2. Mientras haya nodos no visitados:
a. Selecciona el nodo no visitado con la distancia más pequeña (llamémoslo “nodo actual”).
b. Marca el nodo actual como visitado y agrega el nodo al conjunto de nodos visitados.
c. Para cada vecino no visitado del nodo actual:
— Calcula la distancia tentativa desde el nodo de origen hasta el vecino a través del nodo actual.
— Si la distancia tentativa es menor que la distancia actual almacenada en el vecino, actualiza la distancia actual del vecino.
3. Al finalizar, se habrá encontrado el camino más corto desde el nodo de origen hacia todos los demás nodos.
- El algoritmo de Dijkstra se basa en un principio fundamental en el que construye un conjunto de nodos visitados y un conjunto de nodos no visitados. Luego, el algoritmo explora todos los nodos no visitados y actualiza las distancias más cortas conocidas para cada nodo. Esto se hace utilizando los pesos de las aristas entre los nodos.
- En cada iteración del algoritmo, se elige el nodo no visitado con la distancia más corta y se actualizan las distancias de sus nodos adyacentes. Este proceso continúa hasta que todos los nodos hayan sido visitados.
Ejemplo. Pseudocódigo que implementa el algoritmo de Dijkstra
1. Crea un conjunto de nodos no visitados y lo inicializa con todos los nodos del grafo
2. Crea un diccionario de distancias y lo inicializa con infinito para todos los nodos
3. Establece la distancia del nodo origen a 0
4. Mientras el conjunto de nodos no visitados no esté vacío:
4.1. Selecciona el nodo no visitado con la distancia más pequeña (llamémoslo "nodo actual")
4.2. Marca el nodo actual como visitado y remuévelo del conjunto de nodos no visitados
4.3. Para cada vecino del nodo actual:
4.3.1. Calcula la distancia tentativa desde el origen hasta el vecino a través del nodo actual
4.3.2. Si la distancia tentativa es menor que la distancia actual del vecino:
4.3.2.1. Actualiza la distancia actual del vecino con la distancia tentativa
Fin 4.
Este algoritmo encuentra el camino más corto desde un nodo de origen hacia todos los demás nodos en un grafo.
Es importante destacar que, si bien el algoritmo de Dijkstra es eficiente para grafos pequeños o medianos, puede ser ineficiente en grafos grandes debido a su complejidad de tiempo.
En tales casos, existen variantes y mejoras del algoritmo, como el algoritmo A* o el uso de estructuras de datos como montículos binarios (heaps) para mejorar su rendimiento.
- En la carpeta Libros esenciales (en inglés y español) hay material básico y avanzado sobre grafos.
- Dijkstra’s algorithm. Pág. 130
.png)
