ALGORITMO DIJKSTRA

 ALGORITMO DIJKSTRA

Descripción

El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:

• Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
• Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Conjunto C : Conjunto de vértices candidatos. Inicialmente contiene todos los nodos menos el nodo origen. 
Conjunto S : Conjunto de vértices seleccionados, es decir, aquellos para los que ya conocemos su camino mínimo desde el nodo origen. Inicialmente contiene el nodo origen. 
Vector D : Almacenará la longitud del camino más corto desde el origen a cada nodo. Tendrá tantas posiciones como nodos tenga el grafo. El coste de ir del nodo origen a sí mismo lo estimaremos como cero. 
Vector P : Almacenará el nodo predecesor a cada nodo en el camino más corto desde el origen hasta él. Tendrá tantas posiciones como nodos tenga el grafo. La posición del nodo predecesor al origen estableceremos que sea cero para indicar que es el nodo origen.
Llamaremos al nodo origen o, y el coste de ir del nodo i al nodo j lo denotaremos como COSTEij .

Los pasos a seguir para el algoritmo de dijkstra:

 Seleccionamos el nodo que sea destino de la arista con menor valor que salga del nodo o, llamémoslo u. Introducimos el nodo u en S y lo sacamos de C. Almacenamos en la posición u del vector D el valor COSTEou y en la posición u del vector P el valor del nodo predecesor, es decir, o.

Seleccionamos el siguiente nodo al que podamos llegar con menor coste, bien directamente desde o, bien a través del otro nodo seleccionado u. Llamamos al nuevo nodo seleccionado v. Introducimos el nodo v en S y lo sacamos de C. Introducimos en la posición v del vector D el coste de llegar al nodo v, si es directamente desde o será COSTEov, si es a través de u será D[u]+COSTEuv. Por último, en la posición v del vector P introducimos el valor del nodo predecesor, ya sea o o u.

Repetiremos este proceso hasta que todos los nodos hayan sido seleccionados, es decir, hasta que el conjunto C esté vacío, o lo que es lo mismo, hasta que en el conjunto S se encuentren todos los nodos del grafo. En ese momento en el vector D tendremos almacenado el coste mínimo para llegar desde el nodo origen a cualquier nodo del grafo, y podremos obtener el camino más corto mediante el vector P.

 EJEMPLO1:

 EJEMPLO2: