Twelve Days 2013: The Bellman-Ford Algorithm

Day Twelve: The Bellman-Ford Algorithm

TL/DR

If you need to find the shortest path for a graph with negative weights, the Bellman-Ford algorithm can do so. Dijkstra's algorithm has better time complexity, but Bellman-Ford can handle graphs with negative weights, and even be used to detect negative cycles.

Detecting Negative Cycles

Today's post is short and sweet – I might add code later but the algorithm is quite simple. For graphs with negative weights, Dijkstra's algorithm fails. Negative weights introduce the potential for negative cycles, in which case a shortest path might not exist as a shorter path could always be constructed by transversing the cycle once again. That breaks Dijkstra. The Bellman-Ford algorithm can detect this when it happens. Unfortunately, the generality comes at the cost of time complexity. Dijkstra's algorithm runs in $\O(\|E\| + \|V\|\log(\|E\|))$. Bellman-Ford takes $\O(\|E\| \cdot \|V\|))$, where $V$ and $E$ are the sizes of the vertex and edge sets, respectively. There are modifications to Bellman-Ford with slightly better time complexity, but Bellman-Ford is quite simple to implement.

Finding Negative Cycles

Once you know that there is a negative cycle, you still need to find it. There are fast algorithms to do so, but depth-first search (DFS) is arguably the simplest route. You can run DFS on a subgraph that's produced as a bi product running Bellman-Ford (the shortest path edge set that's generated along the way) for slightly better time complexity. There's a break even point between just running depth-first search on the full graph or starting off with Bellman-Ford to check if there's a negative cycle in the first place. The run-time complexity of DFS is exponential for graphs with a branching factor greater than one so it's not cheap. For really small graphs you're almost certainly better off with a vectorized brute force search.

Why do we Care?

Finding a path via DFS, or the shortest path via Bellman-Ford/Dijkstra's algorithm/A-star has lots of applications in optimization and logistics. Here's one nice example. Graphs with negative cycles are a special case of the shortest path problem, and once upon a time, currencies were inefficient enough that triangular arbitrage persisted for some time. These days, it's a purely high frequency game.