El problema de los caminos más cortos es el problema que
consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que
la suma de los pesos de las aristas que lo constituyen es mínima. Ahora bien,
podemos emplear el algoritmo de Dijkstra para éstos casos, los pasos o
procedimientos a seguir para éste algoritmo son los siguientes: Teniendo un
grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un
vector D de tamaño N guardará al final del algoritmo las distancias desde x al
resto de los nodos.
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 vi
4. Si la distancia desde x hasta va guardada en D es mayor
que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta
se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D
(puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al
paso 3 mientras existan nodos no marcados.
No hay comentarios:
Publicar un comentario