ALGORITMO DE DIJKSTRA
CARACTERÍSTICAS:
•Es
un algoritmo Greddy.
•Trabaja
por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias
futuras.
•El
óptimo encontrado en una etapa puede modificarse posteriormente si surge una
solución mejor.
Consideraciones
Si
los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
Recorrido por anchura BFS
Si los pesos de mis aristas son negativos
no puedo usar el algoritmo de Dijsktra.
-1 -2 -5 -3 -10
Como
funciona:
1.Inicializar
todas las distancias en D con un valor infinito relativo ya que son
desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido
a que la distancia de x a x sería 0.
2.
Sea a = x (tomamos a como nodo
actual)
3. Recorremos todos los nodos
adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no
marcados vi.
4. Para el nodo actual, calculamos la
distancia tentativa desde dicho nodo a sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi).
Si la distancia tentativa es menor que la
distancia almacenada en el vector, actualizamos el vector con esta distancia
tentativa.
Es decir: Si dt(vi)
< Dvi → Dvi =
dt(vi)
5.
Marcamos como completo el nodo a.
6.
Tomamos como próximo nodo actual el de menor valor en D (puede hacerse
almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras
existan nodos no marcados.
Referencias
No hay comentarios.:
Publicar un comentario