Algoritmo de Dijkstra para ruta más corta. Ejemplo 1

Algoritmo de Dijkstrapara ruta más corta

Ejemplo 1

()

()

()

()

()

()

()

Cola2

101 3

2

4

5

2

64

1

8

v1, 0

v2, inf

v3, inf

v4, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v1, 0

v2, inf

v3, inf

v4, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v1, 0

v2, 2

v3, inf

v4, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v1, 0

v4,1

v2, 2

v3, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, inf

v5, inf

v7, inf

v6, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, 3

v5, inf

v7, inf

v6, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, 3

v5, 3

v7, inf

v6, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, 3

v5, 3

v6, 9

v7, inf

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v4,1

v2, 2

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v2, 2

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v2, 2

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v2, 2

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

No cambia

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v3, 3

v5, 3

v7, 5

v6, 9

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v3, 3

v5, 3

v7, 5

v6, 8

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v5, 3

v7, 5

v6, 7

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v5, 3

v7, 5

v6, 7

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v5, 3

v7, 5

v6, 7

Cola2

101 3

2

4

5

2

64

1

8

Inicio

No cambia

v7, 5

v6, 7

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v7, 5

v6, 6

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v7, 5

v6, 6

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v6, 6

Cola2

101 3

2

4

5

2

64

1

8

Inicio

v6, 6

Cola2

101 3

2

4

5

2

64

1

8

Inicio

Cola2

101 3

2

4

5

2

64

1

8

Inicio

Cola2

101 3

2

4

5

2

64

1

8

Inicio

Cola2

1

2 2

4

1

Inicio

Ejemplo 2

1

1

1

1

1

11 1

()

()

()

()

()

()

()

1

Cola

1

1

1

1

1

1

11 1

Inicio

(a, 0)

(b, inf)

(c, inf)

(d, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(a, 0)

(b, inf)

(d, inf)

(c, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(a, 0)

(b, 1)

(c, inf)

(d, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(a, 0)

(b, 1)

(d, 1)

(c, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(b, 1)

(d, 1)

(c, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(b, 1)

(d, 1)

(c, inf)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(b, 1)

(d, 1)

(c, 2)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(b, 1)

(d, 1)

(c, 2)

(e, inf)

(d, inf)

1

Cola

1

No cambia

1

1

1

1

1

11 1

Inicio

(d, 1)

(c, 2)

(e, inf)

(d, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(d, 1)

(c, 2)

(e, inf)

(f, inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(d, 1)

(c, 2)

(e, inf)

(f, inf)

1

Cola

1

No cambia

1

1

1

1

1

11 1

Inicio

(d, 1)

(c, 2)

(e, 2)

(inf)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(d, 1)

(c, 2)

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(c, 2)

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(c, 2)

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(c, 2)

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(e, 2)

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

(f, 2)

1

Cola

1

1

1

1

1

1

11 1

Inicio

1

Cola

1

1

1

1

1

1

11 1

Inicio

1

Cola

1

1

1

1

1

InicioCola

1