Mi Tarea

2

1 1 2
4 5

3

7

2
1

3 4 1
6

3

5
8

9

5 1
1 1⎡0 2⎢ 2 ⎢ 3⎢1 ⎢ 4⎢ 3 5 ⎢∞ ⎢ 6 ⎢∞ 7 ⎢∞ ⎢ 8 ⎢∞ 9 ⎢∞ ⎣ 2 3 4 5
3

2

4

3
6 7 8 9

2 1 3 ∞ ∞ ∞ ∞ ∞⎤ Y=N d D i Nodo Destino ⎥ 0 ∞ 1 1 ∞ ∞ ∞ ∞⎥ V = {v / v son los Nodos del Sistema} ∞ 0 5 ∞ 3 ∞ ∞ ∞⎥ ⎥ S = {s / s son los Nodos Solución} 1 5 0 2 1 ∞ ∞ ∞⎥ R = V − S = {r / r son los Nodos Re s tan tes} 1 ∞ 2 0 ∞ 3 4 ∞⎥ ⎥∞ 3 1 ∞ 0 ∞ 2 ∞⎥ D = {di / di son las Dis tan cias Mín a los Nodos Re s tan tes} ∞ ∞ ∞ 3 ∞ 0 5 3⎥ ⎥ di = Min d xi , d xv + d vi ∞ ∞ ∞ 4 2 5 0 4⎥ ∞ ∞ ∞ ∞ ∞ 3 4 0 ⎥ Ter min a cuando S = V o se llega al destino ⎦

X = Nodo Origen

{

}

2

1 1 2
4 5

3

7

2
1

3
4 1
6

3

5
8

9

5
1
1 1⎡0 2⎢2 ⎢ 3⎢1 ⎢ 4⎢3 5 ⎢∞ ⎢ 6 ⎢∞ 7 ⎢∞ ⎢ 8 ⎢∞ 9 ⎢∞ ⎣ 2 3 2 0 ∞ 1 1 1 ∞ 0 5 4 5 ∞ 1 ∞2 0 ∞ 3 4 ∞ 6 7 ∞ ∞ ∞ ∞ ∞ 3 0 ∞ ∞ 0 2 5 ∞ 3 ∞ ∞ 3 1 8 9 ∞ ∞ ∞ ∞ 4 2 5 0 4 ∞⎤ ∞⎥ ⎥ ∞⎥ ⎥ ∞⎥ ∞⎥ ⎥ ∞⎥ 3⎥ ⎥ 4⎥ 0⎥ ⎦ 3 1 5 0 ∞ 2 ∞ 3 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

3

2

4
S = {1}

Y =9 X =1 V = {1, 2,3, 4,5, 6, 7,8,9} ⇒ v = 1, 2,3, 4,5, 6, 7,8,9
R = V − S = {2 3 4,5, 6 7 8 9} ⇒ r = 2 3 4,5, 6 7 8 9 2,3, 4 5 6, 7,8,9 2,3, 4 5 6, 7,8,9

3

di = Min {d xi , d xr + d ri } siendo i = r

d 2 = Min {d12, d12 + d 22 , d13 + d32 , d14 + d 42 , d15 + d52 , d16 + d 62 , d17 + d 72 , d18 + d82 , d19 + d92 } d3 = Min {d13 , d12 + d 23 , d13 + d33 , d14 + d 43 , d15 + d53 , d16 + d 63 , d17 + d 73 , d18 + d83 , d19 + d93 } d3 = Min {1, 2 + ∞,1 + 0,3 + 5, ∞ + ∞, ∞ + 3, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 1 d 2 = Min {2, 2 + 0,1 + ∞,3 + 1, ∞ + 1, ∞ + ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 2

2

1 1 2
4 5

3

7

2
13
4 1
6

3

5
8

9

5
1
1 1⎡0 2⎢2 ⎢ 3⎢1 ⎢ 4⎢3 5 ⎢∞ ⎢ 6 ⎢∞ 7 ⎢∞ ⎢ 8 ⎢∞ 9 ⎢∞ ⎣ 2 3 2 0 ∞ 1 1 1 ∞ 0 5 4 5 ∞ 1 ∞ 2 0 ∞ 3 4 ∞ 6 7 ∞ ∞ ∞ ∞ ∞ 3 0 ∞ ∞ 0 2 5 ∞ 3 ∞ ∞ 3 1 8 9 ∞ ∞ ∞ ∞ 4 2 5 0 4 ∞⎤ ∞⎥ ⎥ ∞⎥ ⎥ ∞⎥ ∞⎥ ⎥ ∞⎥ 3⎥ ⎥ 4⎥ 0⎥ ⎦ 3 1 5 0 ∞ 2 ∞ 3 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

3

2

4
S = {1}

Y =9 X =1 V = {1, 2,3, 4,5, 6, 7,8,9} ⇒ v = 1, 2,3, 4,5, 6, 7,8,9
R = V − S = {2 3 4,5, 6 7 8 9} ⇒ r= 2 3 4,5, 6 7 8 9 2,3, 4 5 6, 7,8,9 2,3, 4 5 6, 7,8,9

3

di = Min {d xi , d xr + d ri } siendo i = r

d 4 = Min {d14 , d12 + d 24 , d13 + d34 , d14 + d 44 , d15 + d54 , d16 + d 64 , d17 + d 74 , d18 + d84 , d19 + d94 }

d 4 = Min {3, 2 + 1,1 + 5,3 + 0, ∞ + 2, ∞ + 1, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 3

d5 = Min {d15 , d12 + d 25 , d13 + d35 , d14 + d 45 , d15 + d55 , d16 + d 65 , d17 + d 75 ,d18 + d85 , d19 + d95 } d5 = Min {∞, 2 + 1,1 + ∞,3 + 2, ∞ + 0, ∞ + ∞, ∞ + 3, ∞ + 4, ∞ + ∞} = 3

2

1 1 2
4 5

3

7

2
1

3
4 1
6

3

5
8

9

5
1
1 1⎡0 2⎢2 ⎢ 3⎢1 ⎢ 4⎢3 5 ⎢∞ ⎢ 6 ⎢∞ 7 ⎢∞ ⎢ 8 ⎢∞ 9 ⎢∞ ⎣ 2 3 2 0 ∞ 1 1 1 ∞ 0 5 4 5 ∞ 1 ∞ 2 0 ∞ 3 4 ∞ 6 7 ∞ ∞ ∞ ∞ ∞ 3 0 ∞ ∞ 0 2 5 ∞ 3 ∞ ∞ 3 1 8 9 ∞ ∞ ∞ ∞ 4 2 5 0 4 ∞⎤ ∞⎥ ⎥ ∞⎥ ⎥ ∞⎥ ∞⎥ ⎥ ∞⎥ 3⎥ ⎥ 4⎥ 0⎥ ⎦ 3 1 5 0 ∞ 2 ∞ 3 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞∞

3

2

4
S = {1}

Y =9 X =1 V = {1, 2,3, 4,5, 6, 7,8,9} ⇒ v = 1, 2,3, 4,5, 6, 7,8,9
R = V − S = {2 3 4,5, 6 7 8 9} ⇒ r = 2 3 4,5, 6 7 8 9 2,3, 4 5 6, 7,8,9 2,3, 4 5 6, 7,8,9

3

di = Min {d xi , d xr + d ri } siendo i = r

d 6 = Min {d16 , d12 + d 26 , d13 + d36 , d14 + d 46 , d15 + d56 , d16 + d 66 , d17 + d 76 , d18 + d86 , d19 + d96 } d 7 = Min {d17 , d12 + d 27 , d13 + d37 ,d14 + d 47 , d15 + d57 , d16 + d 67 , d17 + d 77 , d18 + d87 , d19 + d97 } d 7 = Min {∞, 2 + ∞,1 + ∞,3 + ∞, ∞ + 3, ∞ + ∞, ∞ + 0, ∞ + 5, ∞ + ∞} = ∞ d 6 = Min {∞, 2 + ∞,1 + 3,3 + 1, ∞ + ∞, ∞ + 0, ∞ + ∞, ∞ + 2, ∞ + ∞} = 4

2

1 1 2
4 5

3

7

2
1

3
4 1
6

3

5
8

9

5
1
1 1⎡0 2⎢2 ⎢ 3⎢1 ⎢ 4⎢3 5 ⎢∞ ⎢ 6 ⎢∞ 7 ⎢∞ ⎢ 8 ⎢∞ 9 ⎢∞ ⎣ 2 3 2 0 ∞ 1 1 1 ∞ 0 5 4 5 ∞ 1 ∞ 2 0 ∞ 3 4 ∞ 6 7 ∞∞ ∞ ∞ ∞ 3 0 ∞ ∞ 0 2 5 ∞ 3 ∞ ∞ 3 1 8 9 ∞ ∞ ∞ ∞ 4 2 5 0 4 ∞⎤ ∞⎥ ⎥ ∞⎥ ⎥ ∞⎥ ∞⎥ ⎥ ∞⎥ 3⎥ ⎥ 4⎥ 0⎥ ⎦ 3 1 5 0 ∞ 2 ∞ 3 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

3

2

4
S = {1}

Y =9 X =1 V = {1, 2,3, 4,5, 6, 7,8,9} ⇒ v = 1, 2,3, 4,5, 6, 7,8,9
R = V − S = {2 3 4,5, 6 7 8 9} ⇒ r = 2 3 4,5, 6 7 8 9 2,3, 4 5 6, 7,8,9 2,3, 4 5 6, 7,8,9

3

di = Min {d xi , d xr + d ri } siendo i = r

d8 = Min {d18 , d12 + d 28...