• Author / Uploaded
• Oscar Patricio Morales Rueda

Citation preview

ESCUELA SUPERIOR POLITÉCNICA DE CHIMBORAZO

PROBLEMA DE LA RUTA MAS CORTA

1

Introducción Se trata de un modelo de red (debido a la forma de diagrama de red usado para su representación), donde cada arco o rama que une dos nodos (elementos) que forman dicha red, viene caracterizado por un valor que representa la distancia (costo o tiempo) desde el nodo origen hasta el nodo destino Usualmente los arcos no están orientados, es decir, se permite el tráfico en ambos sentidos, salvo que se indique lo contrario (por ejemplo en una calle de dirección.

¿En que consiste el Modelo de Ruta mas corta? El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodo inicial y el destino o nodo terminal.

DEFINICIÓN DEL PROBLEMA • Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n. • -Arcos bi-direccionales conectan los nodos con distancias mayores que cero. • -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n. • Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

Pasos a seguir: 1. Elaborar un cuadro con todos los nodos y los ramales que salen de él. 2. Partiendo del origen, debemos encontrar el nodo más cercano a él. 3. Anular todos los ramales que entren al nodo más cercano elegido. 4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino

EJERCICIO 1 PASO A PASO • http://investigacionoperativacuarto.blogspo t.com/2013/05/modelo-de-la-ruta-mascorta.html

6

Ejercicio Práctico Carlos envía con frecuencia remesas de vino a 7 localidades diferentes. El considera que el total de sus costos se minimizaría si pudiera asegurarse de que todos los envíos futuros a cualquiera de las localidades se realicen siguiendo la ruta mas corta. Por tanto, su objetivo consiste en especificar cuales son las rutas mas cortas desde el nodo de inicio hasta cualquiera de los otros 7 nodos.

Ejercicio Práctico

Ejercicio Práctico

Planteamiento del problema 7 1 2 8

3

6

4 7

1

H

3

3

5

1

4

1

1 6

2

3

2

Conclusiones • Si denominamos ruta o camino, a cualquier secuencia de arcos que conecte el nodo origen con el destino, la resolución consiste en encontrar la más corta posible.

11