El problema de la Ruta más Corta

Un ejemplo simple para aplicar a este tipo de problemas sería el viaje de una persona desde un estado a ciudad el cual pudiese tener varias alternativas, según el interés de la persona, bien sea para ir más rápido o llegar de manera económica según sus recursos, para el primer caso se minimizaría la distancia y para el segundo caso el costo, en cualquier caso el objetivo consistiría en encontrar la ruta más eficiente a un menor costo, y por lo tanto tendríamos que los estados estarán representados como los nodos y las carreteras como los arcos.

IMPORTANCIA

Este método es muy importante ya que por medio de este modelo se pueden resolver de manera rápida, ya que pueden formularse como modelos de redes obteniendo soluciones enteras sin necesidad de restricciones (aunque en algunos casos pudieran tenerlas), asimismo se puede decir que no importa que tan grande sea el problema se puede resolver por pequeños algoritmos. Por otra parte según la página www.ptolomeo.unam.mx en sus conceptos básicos, capitulo 1 señala la importancia de este método:

El problema de la Ruta más Corta es fundamental en muchas áreas, como son: investigación de operaciones, ciencia de la computación e ingeniería. Algunas de las razones son:

I. La amplia variedad de aplicaciones prácticas como es el envío de algún material entre dos puntos específicos de la forma más eficiente, económica o rápida.

II. Existen métodos de solución eficientes, los cuales al ser aplicados a una red con características específicas (a cíclica y con costos no negativos), proveen una solución exacta a un tiempo y costo razonables.

III. Se puede utilizar como inicio en el estudio de modelos complejos de redes, esto es, cuando no se conoce la estructura de la red se pueden aplicar algoritmos para conocer algunas características de la red (presencia de ciclos negativos).

IV. Se utiliza frecuentemente como sub-problemas (subrutinas) en la solución de problemas combinatorios y redes, así en el caso de problemas para los cuales no existe un algoritmo de solución exacto (p. e. problemas NP-completos), la aplicación de algoritmos de ruta más corta, resultan auxiliares para encontrar una buena solución.

APLICACIONES

En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida practica, dentro de las que podemos mencionar:

•Transporte,

•Horarios de operadores telefónicos,

•Planeación de tráfico urbano,

•Trasbordo,

•En las redes eléctricas,

•Diseño

...