Algoritmos para caminos mínimos

Abstract

En el presente trabajo se estudiará las diferentes aplicaciones prácticas que puede tener El Problema de Caminos Mínimos para problemas de optimización de flujos de redes. Sea el caso en el que nos presenta un problema de decisi´on, el cual tiene como trasfondo decidir cuál podría ser la elección apropiada para optimizar un costo, buscando sea el menor posible a partir de una posición inicial hasta una determinada instancia final o destino, para el cual se presentarán mucho caminos por escoger. Para llegar a dicho resultado es necesario conocer las restricciones y condiciones con las que se deberá proceder para la modelación apropiada del problema. Utilizando entonces la teoría de grafos se puede llegar a obtener un grafo apropiado que nos servirá para la aplicación de los algoritmos que estudiaremos para la obtención del resultado óptimo. Serán entonces los Algoritmos de Dijkstra y el Algoritmo de Bellman-Ford, los que serán seleccionados para su respectivo estudio, analizando su implementación, las restricciones que se presentan para ciertos casos y los distintos comportamientos de su tiempo de ejecución, este último buscando que mejore con la utilización de diferentes estrategias. Es importante recordar que el problema de Caminos Mínimos se presenta en muchas situaciones de aplicación real, como es el caso de transporte, telecomunicaciones, industria, aplicaciones geográficas y planeamientos, lo cual hace relevante su aprendizaje.