Algoritmo Dijkstra

INSTITUTO POLITECNICO NACIONAL
DIRECCION DE CÓMPUTO Y COMUNICIONES DEL IPN.
DIPLOMADO DE DISEÑO E INTERCONEXIÓN DE REDES LAN Y ENRUTAMIENTO BÁSICO

TEMA: ALGORITMO DE DITJKSTRA Y BELLMAN-FORD.

Alumno: José Ramón Martínez Muciño.

ALGORITMO DE DITJKSTRA.
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dadoun vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto devértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, 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óximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).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 vi 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, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos comocompleto 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.
Una vez terminado al algoritmo, D estará completamente lleno
Definición del algoritmo de Dijkstra * Encontrar las rutas más cortas entre un nodo origen dado y todos los demás nodos,desarrollando los caminos en orden creciente de longitud * N = conjunto de nodos en la red * s = nodo origen * T = lista o conjunto de nodos añadidos o incorporados por el algoritmo * w(i, j) = coste del enlace desde el nodo i al nodo j: * w(i, i) = 0 * w(i, j) = ∞ si los dos nodos no se encuentran directamente conectados * w(i, j) ≥ 0 si los dos nodos están directamente conectado* L(n) = coste en curso obtenido por el algoritmo para el camino de mínimo coste del nodo s al nodo n: * Al finalizar el algoritmo, L(n) es el coste del camino de mínimo coste de s a nMétodo del algoritmo de Dijkstra * Paso 1 [Inicialización] * T = {s} el conjunto de nodos incorporado sólo consta del nodo origen * L(n) = w(s, n) para n ≠ s * El coste inicial de las rutasa los nodos vecinos es el asociado a los enlaces * Paso 2 [Obtención del siguiente nodo] * Se busca el nodo vecino que no esté en T con el camino de menor coste * Incorporar el nodo en T * También se incorporará el enlace desde ese nodo hasta un nodo de T que forma parte del camino * Paso 3 [Actualización de los caminos de mínimo coste] * L(n) = min[L(n), L(x) + w(x, n)]para todo n ∉ T * El algoritmo concluye cuando todos los nodos han sido añadidos a TAnotaciones al algoritmo de Dijkstra * Al final, el valor L(x) asociado a cada nodo x es el coste (longitud) de la ruta de mínimo coste de s a x * Además, T define la ruta de mínimo coste desde s hasta cualquier otro nodo * Cada iteración de los pasos 2 y 3 incorpora un nuevo nodo a T: * Define el...