Algoritmo Dijkstra

Paso a paso de ejemplo de calculo de camino mas corto aplicando el algoritmo Dijkstra.

1. Grafos Caminos Mas Cortos

2. Algoritmo Dijkstra Se requiere como entrada un grafo cuyas aristas tengan peso No pueden tener pesos negativos (para este caso usar bellmand-ford) Se utilizara la siguiente etiqueta para identificar los nodos: [Valor Acumulado, Nodo Procedente] iteracion

3. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [Valor Acumulado, Nodo Procedente] iteracion

4. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion Iteracion 0:

5. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion Iteracion 0: 1

6. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 1:

7. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 1: 3 Marcamos el nodo que tenga menor valor acumulado, que tenga etiqueta y que aun no este marcado.

8. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 2: [4,3] 2 [5,3] 2

9. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 2: [4,3] 2 [5,3] 2 Marcamos el nodo que tenga menor valor acumulado, que tenga etiqueta y que aun no este marcado. 2

10. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 3: [4,3] 2 [5,3] 2 2 [3,2] 3

11. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 3: [4,3] 2 [5,3] 2 2 [3,2] 3 Si ya teniamos una etiqueta en el nodo, tachamos la mayor.

12. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 3: [4,3] 2 [5,3] 2 2 [3,2] 3 Marcamos el nodo que tenga menor valor acumulado, que tenga etiqueta y que aun no este marcado.

13. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 4: [4,3] 2 [5,3] 2 2 [3,2] 3 [5,4] 4

14. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 4: [4,3] 2 [5,3] 2 2 [3,2] 3 [5,4] 4 Marcamos el nodo que tenga menor valor acumulado, que tenga etiqueta y que aun no este marcado. En este caso es igual, marcamos el mas cercano al inicio.

15. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 5: [4,3] 2 [5,3] 2 2 [3,2] 3 [5,4] 4 [7,5] 5

16. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 Iteracion 5: [4,3] 2 [5,3] 2 2 [3,2] 3 [5,4] 4 [7,5] 5 Si ya teniamos una etiqueta en el nodo, tachamos la mayor.

17. Ejemplo 1 2 4 3 5 6 2 1 2 2 4 1 3 [0,-] [Valor Acumulado, Nodo Procedente] iteracion [2, 1 ] 1 [1,1] 1 [5,3] 2 2 [3, 2 ] 3 [ 5 , 4 ] 4 RUTA: 1 – 2 – 4 – 6 DISTANCIA: 5

18. Ejercicio en Clase Camino mas corto: A. De 0 a 11 B. De 5 a 4 C. De 1 a 10 D. De 1 a 4 2 5 8 4 9 2 2 2 5 3 7 9 3 9

19. Algoritmo Al final tenemos en el vector distancia en cada posición la distancia mínima del vértice salida a otro vértice cualquiera.