1 Algoritmo de Dijkstra para ruta más corta

2 Ejemplo 1

3 v1 () v4 () v2 () v6 () v3 () v5 () Cola v7 () 2 1013 2 4 5 2 6 4 1 8

4 v1 (0, V1) v4 (inf) v2 (inf) v6 (inf) v3 (inf) v5 (inf) v1, 0 v2, inf v3, inf v4, inf v5, inf v6, inf v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

5 v1 (0, v1) v4 (inf) v2 (inf) v6 (inf) v3 (inf) v5 (inf) v1, 0 v2, inf v3, inf v4, inf v5, inf v6, inf v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

6 v1 (0, v1) v4 (inf) v2 (2, v1) v6 (inf) v3 (inf) v5 (inf) v1, 0 v2, 2 v3, inf v4, inf v5, inf v6, inf v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

7 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (inf) v3 (inf) v5 (inf) v1, 0 v4,1 v2, 2 v3, inf v5, inf v6, inf v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

8 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (inf) v3 (inf) v5 (inf) v4,1 v2, 2 v3, inf v5, inf v6, inf v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

9 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (inf) v3 (inf) v5 (inf) v4,1 v2, 2 v3, inf v5, inf v7, inf v6, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

10 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (inf) v3 (3, v4) v5 (inf) v4,1 v2, 2 v3, 3 v5, inf v7, inf v6, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

11 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (inf) v3 (3, v4) v5 (3, v4) v4,1 v2, 2 v3, 3 v5, 3 v7, inf v6, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

12 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v4,1 v2, 2 v3, 3 v5, 3 v6, 9 v7, inf Cola v7 (inf) 2 1013 2 4 5 2 6 4 1 8 Inicio

13 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v4,1 v2, 2 v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

14 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v2, 2 v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

15 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v2, 2 v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

16 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v2, 2 v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio No cambia

17 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

18 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

19 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (9, v4) v3 (3, v4) v5 (3, v4) v3, 3 v5, 3 v7, 5 v6, 9 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

20 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v3, 3 v5, 3 v7, 5 v6, 8 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

21 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v5, 3 v7, 5 v6, 7 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

22 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v5, 3 v7, 5 v6, 7 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

23 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v5, 3 v7, 5 v6, 7 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio No cambia

24 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v7, 5 v6, 7 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

25 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (8, v3) v3 (3, v4) v5 (3, v4) v7, 5 v6, 6 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

26 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v4) v7, 5 v6, 6 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

27 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v4) v6, 6 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

28 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v4) v6, 6 Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

29 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v1) Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

30 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v4) Cola v7 (5, v4) 2 1013 2 4 5 2 6 4 1 8 Inicio

31 v1 (0, v1) v4 (1, v1) v2 (2, v1) v6 (6, v7) v3 (3, v4) v5 (3, v4) Cola v7 (5, v4) 2 1 22 4 1 Inicio

32 Ejemplo 2

33 a () b () d () e () c () f () 1 1 1 1 1 1 11 1 Cola 1

34 a (0, a) b (inf) d (inf) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (a, 0) (b, inf) (c, inf) (d, inf) (e, inf) (d, inf) 1 Cola 1

35 a (0, a) b (inf) d (inf) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (a, 0) (b, inf) (d, inf) (c, inf) (e, inf) (d, inf) 1 Cola 1

36 a (0, a) b (1, a) d (inf) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (a, 0) (b, 1) (c, inf) (d, inf) (e, inf) (d, inf) 1 Cola 1

37 a (0, a) b (1, a) d (1, a) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (a, 0) (b, 1) (d, 1) (c, inf) (e, inf) (d, inf) 1 Cola 1

38 a (0, a) b (1, a) d (1, a) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (b, 1) (d, 1) (c, inf) (e, inf) (d, inf) 1 Cola 1

39 a (0, a) b (1, a) d (1, a) e (inf) c (inf) f (inf) 1 1 1 1 1 1 11 Inicio (b, 1) (d, 1) (c, inf) (e, inf) (d, inf) 1 Cola 1

40 a (0, a) b (1, a) d (1, a) e (inf) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (b, 1) (d, 1) (c, 2) (e, inf) (d, inf) 1 Cola 1

41 a (0, a) b (1, a) d (1, a) e (inf) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (b, 1) (d, 1) (c, 2) (e, inf) (d, inf) 1 Cola 1 No cambia

42 a (0, a) b (1, a) d (1, a) e (inf) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (d, 1) (c, 2) (e, inf) (d, inf) 1 Cola 1

43 a (0, a) b (1, a) d (1, a) e (inf) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (d, 1) (c, 2) (e, inf) (f, inf) 1 Cola 1

44 a (0, a) b (1, a) d (1, a) e (inf) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (d, 1) (c, 2) (e, inf) (f, inf) 1 Cola 1 No cambia

45 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (inf) 1 1 1 1 1 1 11 Inicio (d, 1) (c, 2) (e, 2) (inf) 1 Cola 1

46 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (d, 1) (c, 2) (e, 2) (f, 2) 1 Cola 1

47 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (c, 2) (e, 2) (f, 2) 1 Cola 1

48 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (c, 2) (e, 2) (f, 2) 1 Cola 1

49 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (c, 2) (e, 2) (f, 2) 1 Cola 1

50 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (e, 2) (f, 2) 1 Cola 1

51 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (e, 2) (f, 2) 1 Cola 1

52 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (e, 2) (f, 2) 1 Cola 1

53 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (f, 2) 1 Cola 1

54 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (f, 2) 1 Cola 1

55 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio (f, 2) 1 Cola 1

56 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio 1 Cola 1

57 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 1 1 11 Inicio 1 Cola 1

58 a (0, a) b (1, a) d (1, a) e (2, d) c (2, b) f (2, d) 1 1 1 1 Inicio Cola 1