Citation preview

Ruta más corta-Investigación de Operaciones II Modelo de la ruta más corta árbol de expansión mínima Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen(nodo 1); identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.

Algoritmo de Dijkstra Sea ui la distancia más corta del nodo fuente 0 hasta el nodo i y se define dij como la longitud de arco (i, j). Entonces el algoritmo define la etiqueta de un nodo inmediato posterior j como [uj, i]=[ui+ dij, i] La etiqueta del nodo de inicio es [0, -], que indica que el nodo no tiene predecesor. j i ij p 1. Las etiquetas de nodos son de dos clases: temporales y permanentes. Una etiqueta temporal se modifica si se puede encontrar una ruta más corta a un nodo. Cuando se ve que no se pueden encontrar mejores, cambia el estado de la etiqueta temporal a permanente. 2. Etiquetar el nodo fuente (nodo 1) con la etiqueta permanente [0, -]. Igualar i=1. 3. Calcular las etiquetas temporales [ui+ dij, i] para cada nodo j al que pueda llegarse desde el nodo i, siempre y cuando j no tenga etiqueta permanente. Si el nodo j ya esta etiquetado con [uj, k] por otro nodo k, y si ui+ dij < uj sustituir [uj, k] por [ui+ dij, i] 5. Si todos los nodos tienen etiquetas permanentes, detenerse. En caso contrario seleccionar la etiqueta [ur, s] que tenga la distancia más corta (ur) entre todas las etiquetas temporales(los empates se rompen arbitrariamente). 6. Hacer i=r 7. Repetir desde el paso 3

Elaborado por: Freydell Alfaro-4M1-Industrial

Ruta más corta-Investigación de Operaciones II 8, 4

5, 3

2

3

2, 1 6

1 4

1

2

2 0, _ 0

4

2

NODO 6 = 3, 2, 1

3

NODO DE ORIGEN 1

5

3, 4

4, 2

2 2 2

2

NODO DE DESTINO

2

9, 5 6

4 2, 1 1

6, 2 2

4 5, 3 3

EJEMPLO DE RUTA MAS CORTA

Elaborado por: Freydell Alfaro-4M1-Industrial

55