El algoritmo de Bellman-Ford como herramienta para la resolución de problemas de programación lineal

Abstract

El problema de los caminos más cortos de fuente única es fundamental en la teoría de grafos y en la optimización combinatoria. Este tipo de problema consiste en encontrar la ruta más corta desde un vértice de origen hacia todos los demás vértices de un grafo, y tiene una amplia variedad de aplicaciones en áreas como redes de transporte, logística y planificacion de recursos. Este trabajo propone un enfoque progresivo: se parte de la formulación del problema en grafos y se demuestran una serie de propiedades de los caminos más cortos. Después, se analiza el algoritmo de Bellman-Ford, junto con la mejora de Yen. Finalmente, se estudia un caso especial de programación lineal que se puede reducir a la resolución de un problema de caminos más cortos con el algoritmo de Bellman-Ford, mostrando así la conexión entre la optimización en grafos y la programación lineal.

The single-source shortest paths problem is essential in graph theory and combinatorial optimization. This type of problem involves finding the shortest path from a source vertex to every other vertex in a graph and has a wide variety of applications in areas such as transportation networks, logistics, and resource planning. This dissertation proposes a progressive approach: it begins with the formulation of the problem in graphs, and proves some important properties of shortest paths. Then, it analyzes the Bellman-Ford algorithm and Yen’s improvement. Finally, it studies a special case of linear programming that can be reduced to solving a shortest path problem using the Bellman-Ford algorithm, thereby showing the connection between graph optimization and linear programming.