algoritmo de Dijkstra

algoritmo de Dijkstra

El algoritmo puede ser descrito como:

N= conjunto de nodos en la red.

S = nodo origen.

M = conjunto de nodos incorporados en un instante t por el algoritmo.

D ij = el coste del enlace del nodo i al nodo j. Teniendo en cuenta que:

Dii = 0;

Dij = infinito si los dos nodos no están conectados directamente.

Dn = coste del camino de coste mínimo desde un nodo s hacia un nodo n que es conocido por el algoritmo.

El algoritmo tiene tres pasos; los pasos 2 y 3 son repetidos hasta que M = N, es decir, se han calculado todos los caminos posibles con todos los nodos de la red.

1.- Inicializar:

M = {s}

Dn = dsn para n<>s

2.- Encontrar el nodo vecino que no está en M tal que 

Dw = min DjDw = min Dj

                 Y j no pertenece a M.

     

      Añadir w a M.

3.- Actualizar el camino de coste mínimo :

Dn = min [ Dn, Dw + dwn] para todo n no perteneciente a M.

   

     Si el último termino es el mínimo, el camino desde s hasta n es ahora el camino desde s hasta w concatenado con el enlace desde w hasta n.