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:

A list of the shortest distances from the start point to every vertex
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.

Here is why the stopping criterion works:

Without negative cycles: After (V-1) relaxations, all shortest paths are stable. No further updates are possible.
With negative cycles: Distances keep decreasing because traversing the cycle repeatedly reduces path cost. Detecting an update in the (V^{th}) iteration signals such a cycle.

Complexity

The complexity of the Bellman-Ford algorithm can be expressed in two ways:

\(O(n^3)\): \(O(n)\) work per sub-problem in searching through the \(n\) vertices that lead to the vertex
\(O(mn)\): In sparse graphs, less work is performed overall because the search will not be \(O(n)\)

This is also evident from the DP formulation of the problem: there are \(O(n^2)\) sub-problems and up to \(O(n)\) time to solve each problem.

SSSP on DAGs

We can make the Bellman Ford algorithm better for certain types of graphs. What we do is that we add the invariant that we only do relaxation if the set of incoming edges already has the correct weights associated to it.

To do this, we do the relaxation operation in sequence of the topological ordering of the graph.

This is reasonable with a DAG because it is acyclic so there is guaranteed to be a topological ordering. This vastly simplifies the problem.

The leads to the following \(O(m+n)\) time algorithm:

def sssp_on_dag(G, s):
	topolist = toposort(G, s) # Runs in O(m + n) time 
	for each node v in topolist (from start to end): # Runs in O(m) time
		Relax all outgoing edges for node v

This is the SSSP algorithm for DAGs with potentially negative edge weights.

This algorithm can also be developed from DP. There is a deep and interesting connection with DP in this problem because all recurrence relations we can solve using DP are DAGs (it is not possible to visit a node more than once and there is a specific direction of movement).

Example problems

Detect Reachable Negative Weight Cycle: With Bellman Ford, this becomes easy because of the guarantee that the algorithm gives us: if we run it for one more cycle, there should not be any changes to the distances if there is no negative weight cycle.
So to detect this negative weight cycle, we just run Bellman Ford \(n\) times and check if there is a change in weights for the last cycle.
Detect any Negative Weight Cycle: The naive approach is to run Bellman-Ford starting from each connected component. But this is inefficient.
Instead, since the graph may be disconnected and you want to find any negative cycle anywhere in the graph, you need to add a super-source connected to every vertex by a 0-weight edge, or initialize all distances to 0.
Here, we create a new vertex \(s'\) and add directed edges (\(s’ → v\)) of weight \(0\) for every original vertex. This keeps the time complexity \(O(mn)\).

Output the Negative Weight Cycle: The naive approach is to take the changes that happen when Bellman Ford is run \(n\) more times. All the changes only happen to nodes in the negative weight cycle.

However, we can store predecessor pointers. This way, after the \(n^{th}\) relaxation we follow predecessor pointers \(n\) steps from any relaxed vertex to land inside the cycle, then traverse until you return to the same vertex. The reconstruction cost is \(O(n)\) plus the cycle length so time complexity is still dominated by the \(O(nm)\) run.

Algorithm FindNegativeCycle(Graph, source):
    1. Run Bellman-Ford(Graph, source) for n iterations (where n = number of vertices).
       - Keep track of predecessor[v] for each vertex v.

    2. If no vertex was updated in the nth iteration:
           Report "No negative cycle."
       Else:
           Let x = any vertex that was updated in the nth iteration.

    3. To ensure x is inside the cycle (not just affected by it):
           Repeat n times:
               x = predecessor[x]

    4. Initialize empty list Cycle.
       Start from x and do:
           current = x
           Repeat:
               Add current to Cycle
               current = predecessor[current]
           Until current == x AND Cycle has more than 1 vertex

    5. Reverse Cycle to get correct order.
       Output Cycle as the negative weight cycle.