This solves the Single Source Shortest Path problem for a graph with negative edges. With negative edges the problem need to be constrained because the presence of negative cycles introduces scope for inconsistency.

If there is a negative cycle there is an arbitrage opportunity using which we can get shorter and shorter paths (infinitely many of them). If a negative cycle exist, the shortest paths approach $-\infin$.

Thus, the output of the SSSP is either:

1. A list of the shortest distances from the start point to every vertex
2. A statement that the graph contains a negative cycle

Development

To develop this algorithm, we make the observation that to find the shortest distance to node $t$, all we need to know is

• The weights ($w_x$) of all the incoming connections to node $t$
• The shortest distance ($d_x$) from the source node to all the nodes $x$ which have a edge that leads to $t$

Then, the shortest path is $\min(w_x+d_x)$. If there was a shorter distance to each of the nodes $x$ that $d_x$ that would constitute the shortest path. So we use already found shortest paths to find shortest paths for subsequent nodes. These shortest paths that we know have $i$ edges if the shortest path to

Another fact we know is that a shortest path uses at most $n-1$ edges (we can show this easily by contradiction: if there are more edges, there must be repeated vertices in the path).

These are the main ideas underlying the Bellman-Ford algorithm.

It suggests that we should iterate on the maximum number of edges used by a path. At the node itself, we store the estimated distance to that node. Initially, this is set of $\inf$. This estimate is updated repeatedly every time we encounter a shorter path that leads to the node.

We call this update the relax operation.

The relax operation (or "edge relaxation") is the fundamental procedure used to update the shortest known distance to a vertex by checking if a better path exists through an adjacent vertex.

Now, all we need to figure out is the order in which to call these relax operations so that we can get the actual shortest path in the most efficient manner possible.

The invariant we want to maintain is that after $i$ iterations, the shortest path to a node that is at most length $i$ has been identified.

This makes the code very simple:

def bellman–ford(G, s):
	dist_est = [an array of all ∞]; set dist_est[s] = 0
	for n - 1 iterations:
		for all edges e = (u, v) in edge_list:
			relax(G, dist_est, u, v)

It might not be immediately obvious how this related to DP.

The sub-problems that Bellman-Ford tries to solve is $D(v, k)$ which are the shortest paths from the start node $s$ to each node $v$ making use of $k$ edges.

The recursive step updates the shortest distance to any node $v$ as the minimum of the previously computed distance to $v$ and the sum of distances to nodes leading to $v$ and the edge weight from those nodes to $v$. This takes $O(n)$ time.

This leads to the insight that the actual number of iterations of Bellman-Ford needed equals the maximum number of edges in any shortest-path origination from the start node $s$.

Outline

• Initialization
  • Set distance to all vertices as ∞ (infinity).
  • Set distance to the source vertex as 0.
• Relaxation Phase

  • Repeat (V-1) times:

    For each edge ((u, v)) with weight (w), update:

    $\text{if } dist[u] + w < dist[v] \quad \Rightarrow \quad dist[v] = dist[u] + w$

  • This ensures shortest paths are correctly computed because the longest possible simple path has at most (V-1) edges.

• Negative Cycle Check (Stopping Criterion)
  • Perform one more iteration over all edges.
  • If any edge can still be relaxed (i.e., $dist[u] + w < dist[v]$), then a negative cycle exists.
  • Reason: after $V-1$ iterations, all shortest paths should be finalized. Any further relaxation implies that distances can be reduced indefinitely, which only happens with a negative cycle.