Combinatorial Optimization (Cook et al.) II: When Least-Cost Dipaths Exist, the Shortest Dipath Cost Equals the Maximum Feasible PotentialTextbook
The shortest path problem asks, in a network whose links carry costs, for a cheapest directed route from a fixed origin to every other point. It is the basic subroutine of network optimization: minimum-cost flow algorithms, matching algorithms and many dynamic programs call it repeatedly, and arc costs that are negative arise naturally, for instance as …