Algoritmo de Dijkstra

Dijkstra en un algoritmo voraz que sirve para hallar la menor distancia entre dos nodos en un grafo conexo, acíclico, dirijido y con costos no negativos en sus aristas.

De esto hay mucho en wikipedia, por lo que solo me voy a limitar a dar algunas consideraciones que, en el estudio de este algoritmo fueron apareciendo a mi vista :D

El algoritmo sirve para hallar el mínimo camino entre un par de nodos o bien si es aplicado a cada par de nodos, obtendremos el mínimo camino entre todo par de nodos.

El algoritmo no necesita ser recursivo, basta usar 3 for anidados (para el caso anterior).

El orden del algoritmo para encontrar el mínimo camino entre un par de nodos es O(n^2) y para encontrar el mínimo entre todo par de nodos (usando Programación dinámica) es el mismo, notar que no depende del tipo de implementación que se use (cola de prioridad ó vector de visitados)


Inicialmente S contiene únicamente el nodo origen y al final contendráá todos los nodos de G.
En cada paso se selecciona aquél nodo de C cuya distancia al origen sea mínima y lo añadimos a S.
Cuando se detiene el algoritmo todos los nodos del grafo pertenecen a S

Pseudo-código

void dijkstra(int fuente, Grafo g, matriz costoAristas){
S = {fuente}
n = cantidadVertices(g)
for(i=0; i //vector de costos
costos[i] = costoAristas[fuente, i] //inicializo el costo desde la fuente hasta los otros vértices ( infinito en el caso que no exista relación)
//vector de camino final (si acaso necesitamos recontruir el camino más corto)
caminoRecorrido[i] = fuente
visitados[i] = 0; //inicializo un vector de nodos visitados
}
visitados[fuente] = 1;//marco a la fuente como visitada

for(i=0; i if(i != fuente){
w = obtenerMinimoVerticeDisponible(g) //esto es : el minimo del conjunto (V - S)
S = S U {w} //agrego el vértice utilizado
visitados[w] = 1 //lo marco como visitado
for(j=0; j if(visitados[j] != 1){
//que es menos costoso, ir directamente -> costos [j] o ir mediante un w intermedio?
if(costos[w] + costoAristas[w, j] < costos[j]){
//es menos costoso ir mediante w
costos[j] = costos[w] + costoAristas[w, j];
caminoRecorrido[j] = w //agrego el nodo utilizado
}
}
}
}
}
}