Redes

RUTA MÁS CORTA

Un algoritmo clásico de Investigación de Operaciones es el de La Ruta más Corta, usado por ejemplo para encontrar en una serie de ciudades conectadas por carreteras, la ruta parallegar de una ciudad a otra, siguiendo una trayectoria mínima. Existen dos tipos principales de algoritmos: Cíclicos y Acíclicos. Los algoritmos Aciclicos son usados en redes que no tienen ciclos, esdecir que no tienen rutas que partiendo de un nodo lo lleven a él mismo de nuevo. Los ciclos son también llamados "lazos".
 
Los algoritmos cíclicos son para las redes que tienen ciclos o lazos... oen español vueltas en redondo. Un ejemplo de un lazo: Si del nodo "A" puedo ir al nodo "B", y del nodo "B" puedo ir al "C" y del "C" al "D" y del "D" puedo retornar al "A" de nuevo, ahí hay un lazo oun ciclo. Las flechas indican en que sentido esta permitido el movimiento.
 
Algoritmo Aciclico:
 
Si la red no tiene ciclos, apliquemos el siguiente algoritmo:
 
Etiquetar cada nodo con elsiguiente formato [distancia desde el nodo inicial, Nombre del Nodo Precedente]. Para el nodo inicial por definición la distancia es cero (la distancia a sí mismo), y el nodo precedente es vacío (ninguno):[0 , ] .

Después para cada nodo, se analiza los nodos que lo preceden por las flechas, se escoge aquel cuya distancia al nodo inicial más la distancia al nodo presente sea mínima. Se etiqueta conla suma, y el nombre del nodo escogido... bueno, esto en carreta es muy enrredador... mejor con un ejemplo, paso a paso.
 
Consideremos la siguiente red:
 
[pic] 
 
Los nodos pueden representansitios (p.e ciudades, facilidades, etc) las flechas (también llamadas Arcos) indican las trayectorias permitidas y sobre ellas estan las distancias (pero también puede representar el costo dedesplazamiento, o el nivel de riesgo, o un producto de ambos).
 
Encontremos la distancia más corta entre el nodo "A" y el nodo "G".
 
1. Rotular el Nodo Inicial : Recordemos el formato del rótulo es :...