Ruta Minima

Investigación    de  Operaciones  II    

PROBLEMA  DE  RUTA  MÍNIMA  
Definición: Dada una red de n nodos ( i ) conectados por ramas ( i, j ), asociadas a un costo Cij; el objetivo es determinar n-1 rutas mínimas, desde un nodo ( i ) fijado como origen, hasta los restantes n-1 nodos.

 Algoritmo  Dijkstra  de  etiquetas,  ruta  mínima  en  red  no  orientada  
El algoritmo de Dijkstrapara ruta mínima utiliza la etiqueta general: ( # Identificación del nodo precedente, acumulación del costo) que se coloca en cada uno de los nodos de la red, ya sea con carácter permanente P o bien temporal t. Los pasos del algoritmo son los siguientes: 1. El nodo origen siempre se etiqueta con: ( -, 0 ) P 2. A partir del último nodo con etiqueta permanente, se etiquetan temporalmente ( t ) todoslos nodos sin etiqueta permanente, conectados directamente al mismo. 3. Se inicia la revisión de las etiquetas temporales (t), en los nodos que tengan dos etiquetas eliminando la de costo mayor, a continuación se comparan las temporales que aún quedan, con el criterio de costo menor se elige una para permanencia. En caso de empate se hacen permanentes las que estén en esa condición. 4. Se repite elprocedimiento desde el paso 2, mientras existan nodos t para hacerlos P y se termina ordenando en tabla, las n1 rutas mínimas encontradas. Ejemplo. Ruta mínima, aplica algoritmo de Dijkstra. La siguiente red es no orientada, con un total de ocho nodos de los cuales se fija como origen al nodo #8. Determine las rutas mínimas desde el origen hasta los 8 - 1 = 7 nodos restantes, utilizando elalgoritmo de Dijkstra.

1. 2.

Se inicia la aplicación del algoritmo en el paso 1 colocando en nodo origen #8 la etiqueta ( -, 0 )P, el cual tiene como nodos directos a #5, #6 y #7. Se procede en el paso 2 al etiquetado temporal con: a. # 5, ( 8, 0 + 14 = 14 )t; b. # 6, ( 8, 0+7 = 7 ) t; c. # 7, ( 8, 0 + 8 = 8 ) t; d. los otros nodos ( 1, 2, 3, 4 ) aún no se etiquetan. Sólo los nodos # 5, # 6 y # 7,tienen etiqueta temporal, En revisión del paso 3 resulta: mínimo costo respectivo (14, 7, 8) = 7 de nodo # 6 pasa a permanente escribiendo así: # 6, ( 8, 7 ) P. C 8,6 = 7, lo que significa que la etiqueta

3. 4.

Se repite desde paso 2, partiendo de nodo # 6 (recién anotado P) que tiene como nodos directos a # 2, 3, 4, 5, 7 resultando las temporales t siguientes: a. #2,(6, 7+15=22); b. #3,(6,7+8=15); c. #4,(6, 7+13=20); d. #5,(6, 7+6=13); etiqueta anterior # 5, ( 8, 0 + 14 = 14 )t; e. #7,(6,7+9 =16); etiqueta anterior # 7, ( 8, 0 + 8 = 8 )t; f. En el nodo #5 se elimina el temporal (8,14)t y del nodo #7, se elimina el temporal (6,16)t, pues tienen dos etiquetas, y estas son las de mayor costo respectivamente. En paso 3 se revisa: mínimo costo en temporal (22, 15, 20, 13, 8) = 8 nodo#7 debe pasar a permanente, anotando así: #7 ( 8, 8) P. C 8,7 = 8, significa que la etiqueta del

5.

II  AGH  /  II  FCM  

Página  1  

 

Investigación    de  Operaciones  II    
6. Hasta ahora, los nodos #8, #6 y #7 tienen etiqueta permanente, los nodos restantes (excepto el #1) tienen etiqueta t temporal. Se inicia una nueva iteración del algoritmo de Dijkstra desde el paso 2,partiendo del nodo #7, último en pasar a permanencia, el cual tiene como único nodo directo el #4 (pues los nodos #6 y 8 ya tienen permanencia), procediendo con su etiqueta temporal: a. #4, ( 7, 8+11=19 ) t. En primera revisión de paso3, resulta eliminada la etiqueta temporal #4, (6, 20)t y se mantiene la etiqueta temporal #4, ( 7, 8+11=19 ) t. La siguiente revisión resulta: mínimo costo ( 22, 15,19, 13 ) = 13 C 6,5 = 6, significa, la etiqueta de nodo #5 pasa a permanente señalando así: # 5 ( 6, 13 ) P. Para continuar conviene anotar que los nodos # 8, 6, 7, 5, tienen permanencia, los nodos # 2, 3, 4, tienen temporal, el nodo # 1 aún no se etiqueta. Partiendo del nodo # 5 se observa que su único nodo directo para etiqueta temporal es el # 2, ya que en los nodos # 6 y # 8, hay permanencia,...