El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
Los métodos de búsqueda de caminos han tenido, hasta esta sección, un planteamiento puramente recursivo, basado en un recorrido en profundidad del grafo. Esto hace que resulten ineficientes para resolver ciertos problemas. Dijkstra propuso un algoritmo iterativo, de complejidad cuadrática, para encontrar los caminos de costo mínimo que parten de un vértice dado y terminan en cada uno de los demás vértices del grafo. Este mismo problema resuelto con el algoritmo recursivo de búsqueda de caminos planteado en una sección anterior sería O(n3).
La misma idea de este algoritmo se puede aplicar para resolver muchos otros problemas sobre grafos, y por esta razón es importante su estudio.
La presentación del algoritmo de Dijkstra se hace en dos etapas. La primera etapa trata el problema de determinar el costo del camino mínimo que parte de un vértice y termina en cada uno de los demás elementos del grafo. La segunda etapa almacena además la secuencia de vértices que conforman dicho camino.
Algoritmo
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
- Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
- Sea a = x (tomamos a como nodo actual).
- Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
- Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
- Marcamos como completo el nodo a.
- Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
Explicación del algoritmo
Dado un grafo a cuyos arcos se han asociado una serie de pesos, se define el camino de coste mínimo de un vértice u a otro v, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de u a v.
El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad O(n2) donde n es el número de vértices) que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. El fundamento sobre el que se asienta este algoritmo es el principio de optimalidad.
Aplicaciónes del algoritmo
Las aplicaciones del algoritmo de Dijkstra son muy diversas y de gran importancia en distintas áreas del conocimiento. Vamos a presentar algunas de ellas.
-
Encaminamiento de paquetes por los routers: Consideremos una red telefónica. En un momento dado, un mensaje puede tardar una cierta cantidad de tiempo en atravesar cada línea (debido a efectos de congestión, retrasos en las conexiones etc.). En este caso tenemos una red con costes en los arcos y dos nodos especiales: el nodo de comienzo y el de finalización, el objetivo aquí es encontrar un camino entre estos dos nodos cuyo coste total sea el mínimo.
-
Aplicaciones para Sistemas de información: Geográficos: extracción de características curvilíneas de imágenes usando técnicas de minimización del camino: La imagen se representa como una matriz de puntos, cada uno con una especial intensidad. Cada nodo se corresponde con un punto (pixel) de la imagen y tiene hasta ocho nodos adyacentes. El peso de los arcos viene dado en este caso por la diferencia de intensidad. Esta técnica presenta un gran ahorro de costes frente a las herramientas existentes actualmente en el mercado que usan métodos de vectorización automáticos.
-
Caminos mínimos en Grafos usando XML y parsers de Java: El concepto de camino es una secuencia de operadores y conectores: un operador será cualquier unidad de proceso de información realizando un algoritmo específico (i.e. conversores digitales, de formato etc.) y un conector será cualquier mecanismo a través del cual los operadores se comunican entre sí. Dado un conjunto de descripciones de operadores y conectores, unos parámetros de optimización (que el usuario queda encargado de introducir) y una serie de requisitos, el sistema se encargará de encontrar un camino óptimo de una entrada establecida hasta un tipo de salida especificada aplicando transformaciones específicas en el menor tiempo posible.
-
Reconocimiento de lenguaje hablado: Un problema que se presenta es el distinguir entre palabras que suenan de manera similar. Se puede construir un grafo cuyos vértices correspondan a palabras posibles y cuyos arcos unan palabras que puedan ir colocadas una al lado de otra. Si el peso del arco corresponde a la probabilidad de que estén así colocadas, el camino más corto en el grafo será la mejor interpretación de la frase.
-
Otras aplicaciones: Enrutamiento de aviones y tráfico aéreo. Tratamiento de imágenes médicas. Problemas de optimización de una función de coste para moverse entre diversas posiciones.
Medievals Trucos 