Algoritmo De Dijkstra

Algoritmo De Dijkstra

Este algoritmo usado para determinar el costo mínimo, es el más implementado en ciertos dispositivos de Hardware. Se encarga de determinar las rutas con el menor costo, desde un nodo origen hacia todos los otros nodos de un grafo.

El algoritmo va pasando por diferentes estados. En el estado K, las rutas más cortas a los K nodos más cercanos han sido determinadas y estos nodos están dentro de un grupo denominado M. En el estado K + 1, un nodo que no está en M y que tiene la ruta más corta desde el nodo origen es incluido en M.

Al final todos los nodos estarán en M, y sus rutas desde el origen habrán sido determinadas.

El algoritmo puede ser formalmente descrito como sigue:

N = número de nodos en el grafo ( red ).

s = nodo fuente

M = grupo de nodos que han sido incorporados por el algoritmo.

dij= Costo del enlace desde el nodo i al nodo j; dii = 0 y dij =

si los dos nodos no están directamente conectados;

dij>= 0 si los dos nodos están directamente conectados.

Dn= costo de la ruta con el menor costo, desde el nodo s al nodo n.

El algoritmo tiene tres pasos; los pasos 2 y 3 son repetidos hasta que M = N. Es decir tales pasos son repetidos hasta que las rutas finales han sido asignadas a todos los nodos de la red:

1. Inicializar:

M = {s}

// Al grupo de nodos M solo se incorpora el nodo origen.

Dn = dsn para n >s

// Los costos de las rutas iniciales hacia los nodos vecinos son simplemente los costos del enlace.

2. Encontrar el nodo vecino que no está en M y que tiene el enlace con menor costo desde el nodo s. El nodo encontrado se incorpora a M.

Encontrar w M tal que Dw = min { Dj } para j M

Insertar w a M.

3. Actualizar las rutas con el costo mínimo:

Dn = min[Dn, Dw + dwm] para todo j M

Sí el último término es el mínimo, la ruta de s a n es ahora la uta desde s a w concatenada con el enlace que va de w a n.

Cada iteración de los pasos 2 y 3 coloca un nuevo nodo en M y define la ruta con costo mínimo desde s hasta ese nodo. Esa ruta solo pasa a través de nodos que están en M.

...