Bellman Ford

Here we discuss the Bellman Ford algorithm for computing shortest path or negative cycle in an undirected weighted graph $G = (V, E, W)$ that contains negative edges.

Recall the Dijkstra algorithm bases on the induction of the number of vertices. The Bellman Ford algorithm, on the other hand, bases on the induction of the number of edges of the shortest path.

Let $P_k = (s, v_1, v_2, .., v_k, t)$ be the shortest path between $s$ and $t$. If we finds the shortest $P_{k - 1} = (s, v_1, v_2, ..., v_{k - 1})$, then we can easily find the path $P_k$. To this end, we define dist[v] the distance from source node $s$ to vertex $v$.

std::vector<int> dist(n, INT_MAX); 
std::vector<int> pred(n, 0);
dist[s] = 0;
for(int i = 0; i < n - 1; ++i) {
    for each edge (u, v) {
        if(dist[u] + w(u, v) < dist[v]) {
            dist[v] = dist[u] + w(u, v);
            pred[v] = u;
        }
    }
}

If the graph does not contain a negative cycle, the above code compute the shortest path correctly. On the other hand, to check the existence of a negative, we could execute an additional iteration after the above code

bool check_negative_cycle() {
     for each edge (u, v) {
        if(dist[u] + w(u, v) < dist[v]) {
            dist[v] = dist[u] + w(u, v);
            pred[v] = u;
            return true;
        }
    }    
    return false;
}

The correctness can be verified as follows: if the graph does not contain negative cycle, the any shortest path contains at most $(n - 1)$-th edges. The value of $dist[v]$ should not change in this $n$-th iteration.

To return a negative cycle, when we find an edge $(u, v)$ such that $dist[u] + w(u, v) < dist[v]$ (in this $n$-th iteration), we can trace the predecessor of $v$ until we encounter a cycle. Notice that this cycle may not necessarily contains $v$. But we claim that this cycle must be negative.

Theorem

Let $C = (v_1, v_2, ..., v_j)$ be the cycle we found, such that $pred[v_i] = pred[v_{i - 1}], \forall 2 \le i \le j$ and $pred[v_1] = v_j$. WLOG, let $v_1$ be the vertex whose value $pred[v_1]$ is updated latest among $pred[v_1], pred[v_2], ..., pred[v_j]$. It holds that

It follows that $\sum_{i = 1}^j dist[v_i] > \sum_{i = 1}^j dist[v_i] dist[v_i] + \sum_{i = 2}^j w(v_{i - 1}, v_i) + w(v_j, v_1)$, which implies that $\sum_{i = 2}^j w(v_{i - 1}, v_i) + w(v_j, v_1) < 0$.