Algoritmo de dijkstra

Algoritmo De Dijkstra

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 dirigido y con pesos en cada arista. Sunombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando seobtiene 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 costouniforme, 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óximasiteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Tenemos un grafo dirigido ponderado de N nodos que aun no son aislados, sea S el nodoinicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde S al resto de los nodos.

1) Inicializando todas las distancias en D con un valor infinito relativo yaque al principio son desconocidas, exceptuando la de S que se debe colocar en 0 debido a que la distancia de S a S sería 0.
2) Sea a = S (tomaremos a como el nodo actual).
3)Recorreremos todos los nodos adyacentes de a menos los nodos marcados, llamaremos a estos vi.
Si la distancia desde S hasta vi guardada en D es mayor que la distancia desde S hasta asumada a la distancia desde a hasta vi; esta se substituye con la segunda nombrada, esto es:si (Di > Da + d(a,vi)) entonces Di = Da + d(a,vi)

Marcaremos como completo el nodo a.6) Tomaremos como próximo nodo actual el de menor valor en D y volvemos al paso 3 mientras existan nodos no marcados. Ya Terminado El Algoritmo, D estará completamente lleno.