Investigacion

PROBLEMA DE RUTA MAS CORTA
Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino a cada ligadura o arco no dirigido se asocia una distancia nonegativa. El objetivo es encontrar la ruta más corta, la trayectoria con la mínima distancia total del origen al destino.
Se dispone de un algoritmo relativamente sencillo paramanejar este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en ordenascendente de sus distancias más cortas, desde el origen el problema queda resuelto desde el momento de llegar al nuevo destino.
Puede considerarse la red de la ruta más corta como unmodelo de transporte con una fuente y un destino. La oferta de la fuente es una unidad y la demanda en el destino es también de una unidad el objetivo es el de minimizar la distanciarecorrida por el flujo de la unidad de la fuente al destino.
PROBLEMAS:
1. Un camión debe repartir concreto de una planta de mezcla preparada a un sitio de construcción. Cada rutaesta designada con dos piezas de información (D, T) donde D es la longitud de la ruta y T es el tiempo que tarda el camión en atravesar el segmento del camión. La velocidad del camiónen cada segmento está decidida por la condición del camino y también por el número y duración de las paradas del camión. ¿ cual es la mejor ruta de la planta de la construcción .2 (1,5) 4 (7,12)
(1., 3)
1 (2,7)(3,20) (6,8) 6


(5,15)
(3,4) 3 (4,10) 5
(1,2)