domingo, 13 de octubre de 2013
Está diseñado para encontrar las rutas más cortas entre el nodo origen y cada uno de los nodos de la red. Este algoritmo es de tipo “greedy” porque en cada iteración elige la mejor opción de las posibles con la esperanza de encontrar así la mejor solución global.
Una característica de este algoritmo e la utilización de etiquetas en cada nodo cuya función es indicar es cada iteración del algoritmo la distancia del origen a dicho nodo. En cada iteración una de las etiquetas será “permanente”, es decir, indicara la distancia mínima final del nodo inicial a dicho nodo.
Pseudocódigo del Algoritmo:
Dijkstra (G,s)
Inicializar
for cada v perteneciente a V[G]
do d[v] = infinito
p[v] = nulo
d[s] = 0
S = vacio
Q = V[G]
mientras Q no vacio
do u = nodo v con min d[v]
S = S unión u 'se añade al conjunto de nodos finalizados
for cada v perteneciente Adyacente u
Relajación
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
Dijkstra (G,s)
Inicializar
for cada v perteneciente a V[G]
do d[v] = infinito
p[v] = nulo
d[s] = 0
S = vacio
Q = V[G]
mientras Q no vacio
do u = nodo v con min d[v]
S = S unión u 'se añade al conjunto de nodos finalizados
for cada v perteneciente Adyacente u
Relajación
if d[v] > d[u] + w(u,v) then
d[v] = d[u] + w(u,v)
p(v) = u
A continuación les presentaremos un vídeo que explica el proceso:
Suscribirse a:
Entradas
(Atom)