DEFINICION:
El algoritmo de Dijkstra, es un algoritmo para la determinacin del camino ms corto dado un
vrtice origen al resto de los vrtices con pesos en cada arista, en un grafo conexo no dirigido.
Su nombre se refiere a Edsger Dijkstra, un fsico y cientfico de la computacin quien lo
describi por primera vez en 1959.
DESCRIPCION:
La idea subyacente en este algoritmo consiste en:
Ir explorando todos los caminos ms cortos que parten del vrtice origen y que llevan a
todos los dems vrtices.
Cuando se obtiene el camino ms corto desde el vrtice origen, al resto de vrtices que
componen el grafo, el algoritmo se detiene.
Este algoritmo es una especializacin de la bsqueda de costo uniforme (BCU), y como tal, no
funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor,
pueden quedar excluidos de la bsqueda nodos que en prximas iteraciones bajaran el costo
general del camino al pasar por una arista con costo negativo).
COMPLEJIDAD:
El Algoritmo de Dijkstra realiza O(n) operaciones (sumas y comparaciones) para determinar la
longitud del camino ms corto entre dos vrtices de un grafo ponderado simple, conexo y no
dirigido con n vrtices.
O(|V|2+|A|) = O(|V|2) sin utilizar cola de prioridad.
O((|A|+|V|) log |V|) = O(|A| log |V|) utilizando cola de prioridad (por ejemplo un
montculo).
Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden
indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se
atendern de modo convencional segn la posicin que ocupen.
Encaminamiento de paquetes por los routers:
En un momento dado, un mensaje puede tardar cierta cantidad de tiempo en atravesar
cada lnea (por ejemplo, por efectos de congestin). En este caso, tenemos una red con dos nodos
especiales, el de inicio y el de llegada. Los pesos de las aristas seran los costes. El objetivo del
algoritmo es encontrar un camino entre estos dos nodos cuyo coste total sea el mnimo.
Sistemas de informacin geogrficos:
Extraccin de caractersticas curvilneas de imgenes usando tcnicas de minimizacin
del camino. La imagen se representa como una matriz de puntos, cada uno con una intensidad.
Cada nodo es un punto (pxel) de la imagen. El peso de las aristas es la diferencia de color.
Enrutamiento de aviones y trfico areo:
Consiste en un agente de solicitudes de viaje software para hacer un programa de vuelos
para los clientes. El agente tiene acceso a una base de datos con todos los aeropuertos y los vuelos
como el nmero de vuelo, el aeropuerto de origen y destino y los horarios de salida y de llegada.
La aplicacin se usa para determinar la hora de llegada ms temprana para el destino dado un
aeropuerto de origen y hora de inicio.
