I remember a classic MIT problem set in computer science where we reduced the problem of finding a "profitable arbitrage loop" in a directed graph to a shortest path problem: imagine a graph where nodes are currencies and edges are exchange rates: we're seeking to find some loop of nodes U,V,W,...U such that the cumulative product of the edge weights is greater than unity.
The trick is to transform the graph by taking the negative log of the edge weights, which turns problem of finding a cumulative product > 1 into one of finding a negative sum loop. Then, you can just run the Bellman Ford algorithm and if it detects a negative cost cycle in the transformed graph, this corresponds to a positive arbitrage cycle in the original graph.
The trick is to transform the graph by taking the negative log of the edge weights, which turns problem of finding a cumulative product > 1 into one of finding a negative sum loop. Then, you can just run the Bellman Ford algorithm and if it detects a negative cost cycle in the transformed graph, this corresponds to a positive arbitrage cycle in the original graph.
I always thought that was a neat application.