El algoritmo de Dijkstra, desarrollado por el científico holandés Edsger Dijkstra en 1956, es un método eficiente y fundamental en la informática para encontrar el camino más corto desde un nodo inicial a todos los demás nodos en un gráfico con pesos no negativos en sus aristas. Este algoritmo se aplica ampliamente en problemas de rutas de redes, como la navegación GPS y el enrutamiento de paquetes en redes informáticas, optimizando así la eficiencia y la velocidad del tránsito de datos. Su simplicidad y efectividad lo convierten en una herramienta imprescindible para resolver problemas complejos de optimización en diversas áreas de la tecnología y la ciencia.
Básicamente, el algoritmo va encontrando sucesivamente los nodos más cercanos (al nodo fuente) hasta analizar todos los nodos de la red.
En la evolución del algoritmo, cada nodo puede encontrarse en uno de los siguientes estados:
- “abierto”, cuando la etiqueta es aún temporal.
- “cerrado”, cuando la etiqueta es permanente.
Utilizaremos además la letra K para denotar el ultimo nodo cuya etiqueta ha sido cerrada y el símbolo * para indicar al predecesor del nodo fuente (s). Así, el algoritmo puede describirse como sigue:
Paso 1: Inicialización
d(s) = 0 p(s) = *
d(j) = infinito j ≠ s
p(j) = -
Considerar al nodo s como cerrado y todos los demás abiertos. Por lo tanto, k = s.
Paso 2: Revisión de las etiquetas de todos los nodos en estado abierto.
Examinar todos los nodos unidos directamente con el nodo k (no considerar aquellos que estén cerrados). Para los que estén abiertos, hacer:
d(j) = Min (d(j); d(k) + C(j,k))
Donde C(j,k) es el costo del arco (j,k).
Paso 3: Búsqueda del nuevo nodo a poner en un estado cerrado.
Entre los nodos abiertos, se escoge el menor d(j). Sea este el nodo j.
Paso 4: Búsqueda del predecesor de i.
Considerar todos los arcos (j,i) que llegan al nodo i desde un nodo j en estado cerrado.
Encontrar entre estos el nodo j* para el que se cumpla la siguiente igualdad:
d(j) – C (j*, i) = d(j*)
Este es el nodo predecesor de i. Hacer p(i) = j*
Paso 5: Cambiar el estado de i a cerrado.
Si todos los nodos están cerrados, PARAR. Si no, hacer k = i y volver al Paso 2.
Observaciones:
Si en el Paso 3 hay empates, escoger arbitrariamente el futuro nodo a poner en estado cerrado.
El algoritmo también puede usarse para encontrar la ruta minima entre el nodo S y un nodo j dado. Lo que cambia es el Paso 5, ya que el algoritmo deberá terminar cuando el nodo j este en estado cerrado.
Una vez terminado el algoritmo, las etiquetas de los nodos permiten obtener las rutas mínimas. Asi, la parte d(j) de la etiqueta indicara el costo de viaje entre s y j y la parte p(j) el nodo predecesor de j en la ruta. De esta forma, buscando de predecesor en predecesor, se llegará a s, habiendo trazado la ruta minima completa.
