Bellman-Ford: Shortest Paths and Negative Cycles

1. The Problem with Negative Weights

Before diving into Bellman-Ford, let's solidify our understanding of why we need it. Dijkstra's algorithm is greedy; it finalizes the path to the "closest" unvisited node at each step. A negative edge could create a "shortcut" that Dijkstra's would miss because it has already marked a node as visited.

2. The Bellman-Ford Idea: Systematic Relaxation

Unlike Dijkstra's priority-queue-driven greedy approach, Bellman-Ford is simpler and more methodical. Its core idea is based on the principle of relaxation, repeated for a specific number of times.

The algorithm works as follows:

1. Initialization: Create a distance array of size V (number of vertices). Set the distance to the source vertex to 0 and all other distances to infinity (Integer.MAX_VALUE).

2. Iterative Relaxation: Repeat the following process exactly V-1 times:

   • Iterate through every edge (u, v) with weight w in the graph.
   • Perform the relaxation step: If the path to v can be shortened by going through u, update it. $$\begin{gathered} \text{if }\text{dist}[u]+w<\text{dist}[v]: \\ \text{dist}[v]=\text{dist}[u]+w \end{gathered}$$

That's it. After V-1 iterations, the distance array will hold the shortest path distances from the source, assuming there are no negative weight cycles.

Why V-1 Iterations?

This number isn't arbitrary. The longest possible shortest path in a graph with V vertices can have at most V-1 edges. If it had more, it would have to contain a cycle.

In the worst-case scenario, where the edges are processed in an "unlucky" order, each iteration of Bellman-Ford guarantees to find the shortest path for at least one more edge along the path. Therefore, after V-1 iterations, we can guarantee that the shortest path of length V-1 has been found.

3. Detecting Negative Weight Cycles

What if a graph has a cycle whose edges sum to a negative value? You could traverse this cycle endlessly, making the path cost smaller each time. In this case, there is no "shortest" path—it's infinitely small.

Bellman-Ford has an elegant way to detect this. We know that after V-1 iterations, all shortest paths should be finalized. What happens if we run the relaxation loop one more time—a V-th iteration?

• No Negative Cycle: If no negative cycle exists, no distances can be improved further. The distance array will not change.
• Negative Cycle Present: If a shorter path is found during this V-th iteration, it means that some vertex's distance was improved. This is only possible if the path involves a negative weight cycle.

So, the full algorithm is:

1. Initialize distances.
2. Relax all edges V-1 times.
3. Perform one final (V-th) relaxation pass. If any distance is updated, a negative cycle exists. Otherwise, the distances are correct.

Let's watch a detailed walkthrough of this entire process.

4. Implementation in Java

For the implementation, we need a way to represent the graph's edges. While an adjacency list works, it's often simpler for Bellman-Ford to just have a list of all edges, since we iterate through them all anyway. We can create a simple Edge class or use a 2D array int[][] edges where each row is [source, destination, weight].

Here's a Java implementation reflecting the algorithm's logic.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class BellmanFord {

    // Represents an edge in the graph
    static class Edge {
        int source;
        int destination;
        int weight;

        Edge(int src, int dest, int w) {
            this.source = src;
            this.destination = dest;
            this.weight = w;
        }
    }

    public static int[] bellmanFord(int V, List<Edge> edges, int source) {
        // Step 1: Initialize distances from src to all other vertices as INFINITE
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // Step 2: Relax all edges |V| - 1 times
        for (int i = 0; i < V - 1; i++) {
            for (Edge edge : edges) {
                // Check for potential integer overflow before adding
                if (dist[edge.source] != Integer.MAX_VALUE &&
                    dist[edge.source] + edge.weight < dist[edge.destination]) {
                    dist[edge.destination] = dist[edge.source] + edge.weight;
                }
            }
        }

        // Step 3: Check for negative-weight cycles.
        // Run the relaxation one more time.
        for (Edge edge : edges) {
            if (dist[edge.source] != Integer.MAX_VALUE &&
                dist[edge.source] + edge.weight < dist[edge.destination]) {
                System.out.println("Graph contains a negative weight cycle");
                // Return an empty array or signal an error
                return new int[]{-1}; 
            }
        }
        
        return dist;
    }

    public static void main(String[] args) {
        int V = 5;
        int source = 0;
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, -1));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 2));
        edges.add(new Edge(1, 4, 2));
        edges.add(new Edge(3, 2, 5));
        edges.add(new Edge(3, 1, 1));
        edges.add(new Edge(4, 3, -3));
        
        int[] distances = bellmanFord(V, edges, source);
        
        if (distances.length > 1) {
            System.out.println("Vertex Distance from Source " + source);
            for (int i = 0; i < V; i++) {
                System.out.println(i + "\t\t" + (distances[i] == Integer.MAX_VALUE ? "Infinity" : distances[i]));
            }
        }

        System.out.println("\n--- Testing with a negative cycle ---");
        List<Edge> negCycleEdges = new ArrayList<>();
        negCycleEdges.add(new Edge(0, 1, 1));
        negCycleEdges.add(new Edge(1, 2, -1));
        negCycleEdges.add(new Edge(2, 3, -1));
        negCycleEdges.add(new Edge(3, 0, -1)); // Cycle 0->1->2->3->0 with weight -2
        
        bellmanFord(4, negCycleEdges, 0);
    }
}

A crucial implementation detail: When checking dist[u] + w < dist[v], if dist[u] is Integer.MAX_VALUE, adding a positive w would cause an integer overflow and wrap around to a negative number, leading to incorrect results. The check dist[edge.source] != Integer.MAX_VALUE prevents this.

For another perspective on the implementation, you can review the following resource.

5. Complexity Analysis

The complexity analysis for Bellman-Ford is very straightforward, which is one of its advantages.

• Time Complexity: The algorithm consists of a main loop that runs V-1 times (plus one extra time for the negative cycle check). Inside this loop, we iterate through all E edges.

  • Total operations ≈ V * E.
  • Therefore, the time complexity is $O(V\cdot E)$. This is slower than Dijkstra's $O(E\log V)$, which is why Dijkstra's is preferred when edge weights are non-negative.

• Space Complexity: We only need an array to store the distances for each vertex.

  • Therefore, the space complexity is $O(V)$. (If you store the edges in a separate list, it's $O(V+E)$, but often the graph representation is part of the input).

Conclusion

You've now added another essential shortest path algorithm to your toolkit. Bellman-Ford is your go-to solution when faced with the possibility of negative edge weights.

Key Takeaways:

• Bellman-Ford finds the single-source shortest paths in graphs that may contain negative edge weights.
• Its core mechanism is to relax every edge V-1 times.
• It can detect negative weight cycles by performing one additional (V-th) iteration and checking if any distance can still be improved.
• The time complexity is $O(V\cdot E)$, making it less efficient than Dijkstra's for graphs without negative edges.

Preview of the Next Lesson:
So far, we have focused on finding the shortest path from a single source. But what if you need to find the shortest path between all pairs of vertices in a graph? You could run Bellman-Ford V times, but there's a more direct and elegant solution. In the next lesson, we will explore the Floyd-Warshall algorithm, which solves the all-pairs shortest path problem using dynamic programming.