La Ruta más Corta (Algoritmo Cicliclo)

 
La diferencia principal del algoritmo acíclico y el cíclico  es que el cíclico permite trabajar con lazos mientras el algoritmo cíclico no lo permite. Por lo tanto el algoritmo cíclico es mucho más general.
 
La idea principal del algoritmo cíclico es muy parecida al del acíclico; pero en este se trabaja con dos tipos de etiquetas: Etiquetas Temporales y Etiquetas Permanentes. El formato de la etiqueta es el mismo: [distancia mínima encontrada al nodo inicial, Nombre del Nodo Precedente].
 
El Algoritmo se describe así:

  • Rotular todos los nodos a los que se puede llegar desde el nodo inicial con etiquetas temporales, la etiqueta que se les pondrá será [distancia desde el nodo inicial, Nombre del Nodo Inicial].  Aquí no nos va a importar que estos nodos tengan caminos desde otros nodos diferentes al nodo inicial, a diferencia del algoritmo anterior. Sencillamente se rotulan como se describió.

  • Evaluar de todas los nodos con etiquetas temporales, cual posee la distancia más corta en la etiqueta. Marcarlo como Etiqueta Permanente (para esto puede usar  un asterisco).

  • Etiquetar todos los nodos a los que se pueda llegar desde el último nodo con etiqueta permanente, si ya tienen una etiqueta temporal, esta se reevalúa con respecto a la distancia del nodo permanente con que se está trabajando. Si la distancia que da (o sea la distancia de la etiqueta permanente + la distancia al nodo evaluado ) es menor que la que tiene en la etiqueta ésta es cambiada por una nueva etiqueta con la distancia calculada a la de la etiqueta permanente.

  • Se chequean todas las etiquetas temporales existentes, la que tenga la distancia más pequeña se marca como etiqueta permanente y se repite el paso anterior hasta que todas las etiquetas sean permanentes.  do you got it?

 
 
Ejemplo:

Supongamos que existen 7 ciudades interconectadas (o sitios cualquiera: barrios en una ciudad, departamentos en una fabrica, etc.), cada línea representa la trayectoria permitida de una ciudad a otra. Las distancias (o costo de transporte) entre ciudades esta representado por un valor sobre la línea. Se pregunta por la secuencia de ciudades que dan la distancia mínima entre la ciudad A y la ciudad G.
 

 
Paréntesis: Este método como muchos de Investigación de Operaciones, es práctico cuando el número de combinaciones es muy grande como para que una enumeración exhaustiva sea mejor. Por ejemplo, en la red anterior se puede fácilmente de una manera visual, evaluar cuál es la ruta más corta, sin tener que apelar a algoritmos de etiquetado, ni Disktra, ni nada de eso... bueno y entonces como para que o que, nos desgastamos, yo escribiendo esto, y usted leyéndolo?  Pues por que una cosa son míseros 7 nodos, y otra cosa muy diferente serían 100... así que sigamos adelante!

Etiquetar todos los nodos a donde pueda llegar desde el nodo inicial: Es decir los nodos B, C y D.
Etiqueta para el nodo B: Es  distancia desde el nodo que viene = 4, nombre del nodo que viene = "A"
Etiqueta= [4,"A"] , de manera análoga para el nodo C = [5, "A"] y el nodo D = [3, "A"] 
 

 
2. Evaluar cual de todas las etiquetas temporales, tiene la mínima distancia para que sea convertida en etiqueta permanente. Marquemos como etiqueta permanente, con un asterisco. En nuestro caso hay tres etiquetas temporales, [4,"A"], [5,"A"] y [3,"A"]. La que tiene la menor distancia es [3,"A"] en el nodo D. La convertimos en etiqueta permanente.
 

 

3. Ahora, con base en la ultima etiqueta permanente (la del nodo D por supuesto),  se etiquetan todos los nodos a los que se pueda llegar desde el Nodo D (el de la última etiqueta permanente). En nuestro caso, son los Nodos C y F.  La etiqueta para el Nodo F es [3+7=10, "D"], es decir [10, D], para el Nodo C, se puede colocar la etiqueta [3+2, "D"] =  [ 5 ,"D"].  Da igual dejar la etiqueta actual, que tiene una distancia de 5, que cambiarla por esta última. Como se dice por acá: "nos resbala", así que dejemos la que tiene actualmente.
 

 

4. De nuevo se evalúa de todas las etiquetas temporales, cual es la que tiene la distancia más pequeña:[4,"A"], [5,"A"] y [10,"A"].  El nodo B que tiene la etiqueta temporal con la distancia más pequeña, se pasa a tener una etiqueta permanente.
 
 

 

5. Etiquetar todos los nodos a los que se puede llegar desde el nodo con la última etiqueta permanente, es decir el B. Estos nodos son el C y el E. La etiqueta probable para el nodo C sería [4+3, "B"]= [7,"B"], pero como ya tiene una etiqueta temporal de [5,"A"], que tiene una distancia menor, pues ni soñamos con cambiarla!!! Dejémosla quietecita y miremos el Nodo E. La etiqueta para el Nodo E es [4+6, "B"] = [10, "B"]  
 

 

6. Evaluar de todas las etiquetas temporales, cual es la que tiene la distancia más corta: [10,"B"], [5,"A"] y [10,"D"]. La de menor distancia es la [5,"A"]. La marcamos como etiqueta permanente. Ahora etiquetar todos los nodos a los que se puede llegar desde el Nodo C y que no tengan ya, una etiqueta permanente. Estamos hablando del Nodo E, F y G.  Para el Nodo E la etiqueta sería [5+4,"C"] =[9,"C"], que nos da una distancia menor que la que tiene ([10,"B"]). Por lo tanto la cambiamos.  Para el Nodo F nos da [5+5,"C"]=[10,"C"], como ya tiene una etiqueta con 10, nos es indiferente y no la cambiamos.  Para el Nodo G la etiqueta es [5+25, "C"]=[30,"C"].
 
 
7. Evaluar cual de las etiquetas temporales tiene la distancia más corta: [9,"C"], [10, "D"] y [30,"C"]. Gana el nodo  E.  Lo marcamos como etiqueta permanente y desde él evaluamos para rotular a todos los nodos a los que pueda llegar, con etiquetas temporales:  F y G. Para el Nodo F, lo dejamos como esta por que la distancia nos da 9+6 = 15 que es mayor que el que tiene actualmente 10, pero para el Nodo G el rotulo es  [9+7,"E"] = [16, "E"].
Quedan como rótulos temporales el del nodo F y G. El menor es el del Nodo F, se marca como permanente... no hay más rótulos temporales excepto el del Nodo G y el Nodo G quedaría como [10+8, "G"]=[18,"G"] que es mayor que el que ya tiene, así que mejor dejémoslo quietico y por último marquémoslo como etiqueta permanente.
 


Ya podemos leer la trayectoria que da una mínima distancia: G-E-C-A, con una distancia mínima de 16.

Contenido :

Social