ABSTRACT
Finding a least-cost path from one node to another in a graph with arc costs is a special kind of network problem, traditionally called a shortest path problem. Many real-world problems contain shortest-path subproblems. Also, some real-world problems can be modeled as shortest path problems. A great many real problems can be modeled in principle as shortest path problems, but only on graphs that are too large to be computed or stored explicitly. The main negative-cycle detection algorithms are all so closely related to shortest path algorithms that study the following problem: Given a graph with arc weights and distinguished node, find a shortest simple path for each, or find a negative cycle. In financial engineering, such a cycle could represent an arbitrage possibility to be exploited vigorously until a market correction sets in. In most other applications, an unbounded optimum signals an error in the model or data.
