Ruta mínima

A nuestro
alrededor existen
diversos sistemas
que pueden ser
modelados como
redes

Dentro de las medidas que
permiten clasificar a las
redes, podemos encontrar la
ruta más corta; definidacomo
la forma más rápida de llegar
de un punto a otro de la red

Este
problema es
fundamental
en muchas
áreas, como
son:

Investigación de operaciones

Ciencia de la computaciónIngeniería.

Debido a:

Su amplia variedad de aplicaciones prácticas

La existencia de métodos de solución que proveen una solución exacta a
un tiempo y costo razonables.
La posibilidad deutilizarlo como inicio en el estudio de modelos complejos
de redes.
Su utilización como auxiliar en la búsqueda de soluciones a problemas
para los que no existe un algoritmo exacto, mediante subrutinas.Este problema consiste en
encontrar la ruta con menor
longitud entre dos nodos
específicos

Se presenta en actividades
donde se requiere encontrar la
ruta más corta entre dos nodos
de unared:
• Cada arco tiene un costo asociado,
• Objetivo: minimizar el costo (costo,
tiempo, longitud, etc.) total.

Uno de los problemas más
importantes de optimización
combinatoria.

Losalgoritmos para este tipo
de problemas han sido
estudiados desde la época de
los 50’s y continúan siendo un
área activa de investigación

Es posible encontrar el
problema de la ruta más
corta detres formas
distintas:

Del nodo fuente s al nodo
sumidero t. En este caso
debe existir al menos una
ruta entre s y t.

Del nodo fuente s a todo
nodo de la red i. Deben
existir rutas de s a i.Problema de árbol de rutas
más cortas (Shortest Path
Tree SPT).

Entre todo par de nodos,
debe existir, al menos, una
ruta entre todo par de
nodos.

En los tres casos
mencionados, para queexista solución no pueden
existir circuitos negativos
en la red

t

Minimizar

t

 c

ij

xij

i 1 j 1

sujeto a:



xij   xki  
 k 1
j 1


t

t

xij...