Java Bellman Ford Algorithm for Negative Edges

Introduction

The java bellman ford algorithm is the single source shortest path algorithm that handles negative edge weights and detects negative cycles. It was first published by Richard Bellman in 1958 in the paper "On a Routing Problem" in the Quarterly of Applied Mathematics, where he applied dynamic programming to a network routing problem. Lester Ford Jr. published the same algorithm in his 1956 RAND Corporation report "Network Flow Theory", and the algorithm now carries both names. Edward F. Moore independently rediscovered it in 1957, so some textbooks call it the Bellman Ford Moore algorithm.

For a Java learner, the java bellman ford algorithm is the natural follow up to Dijkstra. Where Dijkstra's priority queue pops vertices in non decreasing distance order, Bellman Ford simply relaxes every edge V minus 1 times, which guarantees that the shortest path of at most V minus 1 edges has been found. The cost is O(V times E), which is slower than Dijkstra's O((V plus E) log V) but the algorithm works on graphs with negative edges and detects negative cycles, which Dijkstra cannot.

What is Bellman Ford?

Bellman Ford is a single source shortest path algorithm that works on directed graphs with arbitrary edge weights, including negative weights. It belongs to the family of label correcting algorithms, which means that the distance label of a vertex can be updated many times before it converges to the final value. This is the opposite of label setting algorithms like Dijkstra, where the distance is final once the vertex is popped.

The key insight is the path length bound. In a graph with V vertices, no shortest path can have more than V minus 1 edges, because any path with V or more edges must repeat a vertex and therefore contains a cycle, which adds weight. If all cycle weights are non negative, the cycle can be removed to get a shorter or equal path, so the shortest path has at most V minus 1 edges. Relaxing every edge V minus 1 times therefore propagates the correct distance along any shortest path.

If after V minus 1 relaxations we can still relax an edge, then a negative cycle exists in the graph reachable from the source. A negative cycle is a cycle whose total weight is negative, which means there is no shortest path because we can always go around the cycle one more time to reduce the distance. Bellman Ford detects this in one extra relaxation pass: if any edge can still be relaxed, the graph has a negative cycle.

How Bellman Ford Works - Step by Step

Step 1: Choose a source vertex s. Initialise a distance array of size V with infinity, set distance[s] to zero, and create a parent array of size V initialised to negative one. The parent array records the predecessor on the current best path.

Step 2: Relax every edge V minus 1 times. One relaxation pass walks every edge u to v with weight w, and if distance[u] plus w is less than distance[v], updates distance[v] to distance[u] plus w and sets parent[v] to u. After V minus 1 passes, the distance to every vertex reachable from s along a path of at most V minus 1 edges is final.

Step 3: Run one more relaxation pass. If any edge can still be relaxed, the graph contains a negative cycle reachable from s, and the algorithm reports it. The vertices that lie on or downstream of a negative cycle have undefined shortest distances, because we can always drive the distance lower by going around the cycle one more time.

Step 4: For graphs where you want the shortest path to a specific target, stop early when the distance of the target stops changing between passes. This is a common optimisation that does not change the worst case bound but speeds up practice on sparse graphs.

Step 5: Reconstruct paths using the parent array, but only for vertices that are not on or downstream of a negative cycle. For vertices downstream of a negative cycle, the parent array may form a cycle itself, so path reconstruction may loop forever without a visited check.

Java Program for Bellman Ford

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

public class BellmanFordDemo {

    static class Edge {
        int from;
        int to;
        int weight;
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    // Returns the distance array. If a negative cycle reachable from the
    // source exists, throws IllegalStateException. The parent array is
    // filled in place so the caller can reconstruct paths.
    public static int[] bellmanFord(List<Edge> edges, int n, int source,
                                    int[] parent) throws IllegalStateException {
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        distance[source] = 0;

        // Step 2: relax every edge V - 1 times.
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                if (distance[e.from] != Integer.MAX_VALUE
                        && distance[e.from] + e.weight < distance[e.to]) {
                    distance[e.to] = distance[e.from] + e.weight;
                    parent[e.to] = e.from;
                    updated = true;
                }
            }
            // Early exit if no relaxation succeeded in this pass.
            if (!updated) {
                break;
            }
        }

        // Step 3: one extra pass to detect negative cycles.
        for (Edge e : edges) {
            if (distance[e.from] != Integer.MAX_VALUE
                    && distance[e.from] + e.weight < distance[e.to]) {
                throw new IllegalStateException(
                    "Graph contains a negative cycle reachable from source");
            }
        }
        return distance;
    }

    public static void main(String[] args) {
        int n = 5;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 6));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(2, 1, -3));
        edges.add(new Edge(1, 3, 1));
        edges.add(new Edge(2, 3, 5));
        edges.add(new Edge(3, 4, 2));

        try {
            int[] parent = new int[n];
            int[] distance = bellmanFord(edges, n, 0, parent);
            System.out.println("Vertex  Distance  Parent");
            for (int v = 0; v < n; v++) {
                System.out.printf("  %d       %3d       %d%n",
                                  v, distance[v], parent[v]);
            }
        } catch (IllegalStateException ex) {
            System.out.println(ex.getMessage());
        }
    }
}

Code Explanation - Line by Line

The Edge class holds the source, destination, and weight of a directed weighted edge. Unlike Dijkstra, Bellman Ford takes its input as a flat edge list, because the algorithm walks every edge in a single linear pass per relaxation round, which is exactly the structure of an edge list.

The method starts by initialising the distance array to Integer.MAX_VALUE, which is the standard sentinel for unreachable vertices. The source is set to zero, and the parent array is initialised to negative one. The Integer.MAX_VALUE sentinel must be handled carefully: when we add an edge weight to Integer.MAX_VALUE, the result overflows to a negative number, which would corrupt the relaxation. The check distance[e.from] not equal to Integer.MAX_VALUE prevents this overflow.

The outer loop runs V minus 1 times. The inner loop walks every edge and relaxes it. The boolean updated flag tracks whether any relaxation succeeded in this pass. If no relaxation succeeded, then the distance array has converged and we can break out early, which is the standard early exit optimisation that makes Bellman Ford fast in practice on sparse graphs.

The detection pass after the main loop is identical in structure to a single relaxation pass. If any edge can still be relaxed after V minus 1 rounds, then a negative cycle exists reachable from the source, because a shortest path with V or more edges can only exist if a cycle has negative weight. The method throws IllegalStateException so the caller can handle the negative cycle case explicitly.

The main method builds a small graph with five vertices and six edges, including a negative edge from vertex 2 to vertex 1 of weight negative 3. The shortest path from 0 to 1 is 0 to 2 to 1 with total weight 4 plus negative 3 equals 1, which beats the direct edge 0 to 1 of weight 6. This is the case Dijkstra cannot handle and Bellman Ford can.

Sample Input and Output

Input:  Directed weighted graph with 5 vertices and 6 edges:
        0 -> 1 (weight  6)
        0 -> 2 (weight  4)
        2 -> 1 (weight -3)
        1 -> 3 (weight  1)
        2 -> 3 (weight  5)
        3 -> 4 (weight  2)
        Source vertex: 0

Output:
Vertex  Distance  Parent
  0         0      -1
  1         1       2
  2         4       0
  3         2       1
  4         4       3

The output shows that vertex 1 is at distance 1, not 6, because the path 0 then 2 then 1 with weight 4 plus negative 3 equals 1 beats the direct edge 0 then 1 of weight 6. The negative edge from 2 to 1 is what makes this graph unsolvable by Dijkstra but solvable by Bellman Ford. Vertex 3 is at distance 2 via 0 then 2 then 1 then 3, which is shorter than the direct 0 then 2 then 3 of weight 4 plus 5 equals 9.

Common Mistakes to Avoid

First, do not add an edge weight to Integer.MAX_VALUE without a sentinel check. Adding any positive weight to Integer.MAX_VALUE overflows to a negative number, which would then pass the less than check and corrupt the distance of the destination vertex. Always check that distance[e.from] is not the sentinel before doing the addition.

Second, do not run only V minus 1 relaxation passes and assume there is no negative cycle. The V minus 1 passes compute the shortest path assuming no negative cycle, but you must run one extra pass to detect the negative cycle. Without the extra pass, you return garbage distances that decrease further if you keep relaxing.

Third, do not stop the early exit early. The early exit must check that no relaxation succeeded in an entire pass, not that a particular vertex's distance stopped changing. A vertex that converged in this pass may still relax its neighbours, so the only correct early exit condition is the global updated flag.

Fourth, do not call Bellman Ford on an undirected graph with a negative edge. Every undirected edge is two directed edges, so an undirected edge of weight negative 3 is a two vertex negative cycle. Convert undirected graphs to directed by replacing each undirected edge with two directed edges, and detect negative cycles accordingly.

Real-World Applications

Bellman Ford is used in the Routing Information Protocol version 2, which was the dominant interior gateway protocol before OSPF displaced it. RIP uses a distance vector algorithm that is a distributed variant of Bellman Ford, where each router advertises its distance vector to its neighbours. The count to infinity problem in RIP is exactly the slow convergence of Bellman Ford in the presence of an edge cost increase.

In financial arbitrage detection, Bellman Ford is run on a currency exchange graph where vertices are currencies and edges are exchange rates stored as negative logarithms of the rate. A negative cycle in this graph corresponds to a positive arbitrage opportunity: a sequence of exchanges that returns more currency than it started with. This application is the canonical example of using Bellman Ford for negative cycle detection rather than shortest path computation.

In constraint solvers and difference logic, Bellman Ford is used to detect inconsistency in systems of difference constraints of the form x minus y is at most c. Each constraint becomes an edge y to x of weight c, and a negative cycle in this graph means the system is unsatisfiable. The Bellman Ford computation produces a feasible solution if one exists.

In game development, Bellman Ford is used to compute reachable distance fields on tile grids that include speed boost tiles with negative weight, which Dijkstra cannot handle. The classic example is a level where a boost pad makes the player faster for a few tiles, modelled as negative edge weight, and the path planner must find the route that exploits the boost.

Conclusion

We built Bellman Ford with a flat edge list, V minus 1 relaxation passes, an early exit flag, and one extra pass for negative cycle detection. We learned that the algorithm finds shortest paths even with negative edges, that it detects negative cycles in one extra pass, and that the sentinel overflow check is essential. Next, study Floyd Warshall for all pairs shortest path and A star search for the heuristic guided single target variant.