EJERCICIO 2 - SEGUNDO CORTE

2.  Aplique las iteraciones apropiadas del algoritmo de Dijkstra, para hallar la ruta mínima desde el nodo 1 hasta el 8, para el siguiente grafo.

SOLUCION

V= (1, 2, 3, 4, 5, 6, 7,8)

S= (1)

D [2]=25; D [3]=24; D [4]=12; D [5]= ∞; D [6]= ∞; D [7]= ∞; D [8]= ∞

P[i]= 1i

Primera Iteración

V-S = {2, 3, 4, 5, 6, 7,8}

W = [4]  V-S {2, 3, 5, 6, 7,8}

D[2]= min (D[2] D[4], + C[2,4]=min(25,22)=22

P=2

D [3] = min (D [3] D [4], + C [3, 4] =min (24, ∞) =24

P=4

D [5] = min (D [5] D [4], + C [5, 4] =min (∞, ∞) = ∞

P=5

D[6]= min (D[6] D[4], + C[6,4]=min(∞, 32)=32

P=4

D[7]= min (D[7] D[4], + C[7,4]=min(∞, ∞)= ∞

P=7

D[8]= min (D[8] D[4], + C[8,4]=min(∞, ∞)= ∞

P=8

Segunda Iteración

V-S = {2, 3, 5, 6, 7,8}

W = [2] s= (1, 4, 2) V-S= {3, 5, 6, 7,8}

D[3]= min (D[3] D[2], + C[3,2]=min(24, ∞ )=24

P=3

D[5]= min (D[5] D[2], + C[5,2]=min(∞,42)=42

P=2

D[6]= min (D[6] D[2], + C[6,2]=min(∞, 32)= 32

P= 6

D[7]= min (D[7] D[2], + C[7,2]=min(∞,∞)=∞

P=7

D[8]= min (D[8] D[2], + C[7,2]=min(∞,∞)=∞

P=8

Tercera Iteración

V-S = {3, 5, 6, 7}  

W = [3] s= (1, 4, 2, 3) V-S={5, 6, 7}

D[5]= min (D[5] D[3], + C[5,3]=min( ∞ ,42)=2

P=3

D[6]= min (D[6] D[3], + C[6,3]=min(∞,26)=26

P=3

D[7]= min (D[7] D[3], + C[7,3]=min(∞,∞)=∞

P= 7

D[8]= min (D[8] D[2], + C[7,2]=min(∞,∞)=∞

P=8

Cuarta Iteración

V-S = {5,6,7}

W = [6] s=(1,4,2,3,6) V-S={5,7}

D[5]= min (D[5] D[6], + C[5,6]=min( 42, ∞ )=42

P=5

D[7]= min (D[7] D[6], + C[7,6]=min(∞,∞)=∞

P=7

D[8]= min (D[8] D[6], + C[7,6]=min(∞,∞)=∞

P=8

Quinta Iteración

V-S = {5,7,8}

W = [5] s= (1, 4, 2, 3, 6, 5) V-S= {7}

D[7]= min (D[7] D[5], + C[7,5]=min( 52,55)=52

P=5

Ruta Optima = 1 – 8 (1, 4, 5, 6,7,8)