Path Optimization
Gérard-Michel Cochard, Mhand Hifi · 2025
This chapter presents a first application of graph theory: finding the shortest or longest path. It explores several solution methods, including the level method, enumeration method, Bellman-Ford algorithm, Bellman-Kalaba algorithm and Dijkstra algorithm. Assignment problems are also related to traffic issues, as they involve optimal matching, such as allocating “resources” to “tasks” in the most efficient way. The Bellman-Ford algorithm was historically the first algorithm developed to optimize the search for an extremal path. The principle of the algorithm involves assigning weights to the vertices of a graph. Also referred to as the Moore-Dijkstra algorithm, Dijkstra's algorithm is more efficient than its predecessors and is specifically designed to identify paths of minimum length. It has wide application in route minimization and is extensively used in Global Positioning System navigation. The classic Traveling Salesman Problem involves finding a minimum-length Hamiltonian circuit in a complete graph.