Bellman-Ford algorithm

Dynamic programming solution to the Single source shortest path problem that can also detect negative weight cycles, which means it won’t get stuck in an infinite loop like Dijkstra’s algorithm.

Problem

Input: graph $G=(V,E)$ with weights $w:E\to \mathbb{R}$ with potential negative weight edge cycles, source vertex $s$, target vertex $t$.

Output: shortest path from $s$ to $t$, otherwise a negative weight cycle has been detected.

Intuition, top-level question

From Characterizations about optimal shortest paths, we know all subpaths in the shortest path $p:s\to t$ are also shortest paths. This naturally leads to an algorithm where we find a potential shortest subpath and build on top of it to find the shortest path for $s\to t$.

The shortest path for $t$ uses at most $n$ vertices, and is therefore at most of length $n-1$ (this can happen if, for example, our graph was simply a line). So we need to cover every case less than or equal to that.

• To enable DP, generalize this for a path of any length $l\le n-1$. This way we can slowly build up to $n-1$ (if we’re doing bottom-up).
• Then, the shortest path from $s$ to $t$ using at most $l$ hops is the shortest path of $s\to v$ using $l-1$ hops, plus the weight of $w(v,t)$, where $v\in N(t)$, the neighbors of $t$.
• It could be the case that $s\to t$ with $l-1$ hops is shorter. So the final answer takes the minimum of the two.

$G$-function

The $G$-function is as follows:

$$\begin{array}{rl}G(t,k)& =\text{length of shortest path }s\to t\text{ using at most }k\text{ hops}\\ & =\underset{v\in N(t)}{\min }\left\{G(v,k-1)+w(v,t),G(t,k-1)\right\}\end{array}$$

Base case occurs when $k=0$, in which we case we check if $s=t$. If yes, then return 0 (distance to itself is zero). Otherwise, return infinity.

Algorithm

The $G$-function describes the algorithm in a top-down manner. In practice, Bellman-Ford is usually implemented bottom-up.

1. Maintain the shortest path from $s$ to all other vertices $t\in V$ in a function $d(t)$ which records the length of the shortest path $s\to t$.
2. Initialize $d(s)=0$ and $d(t)=\infty$ for all other $t\in V$.
3. We repeat for $n-1$ rounds. In each round, iterate through every edge $(u,v)\in E$ and update $d(v)\leftarrow \min \{d(u)+w(u,v),d(v)\}$.