Bellman Ford Algorithm Negative Weights in DSA Java

Mental Model

We find the shortest path from one point to all others even if some paths reduce distance by going backward (negative weights). We keep updating distances until no better path is found or we detect a loop that keeps reducing distance.

Analogy: Imagine you are traveling between cities connected by roads. Some roads might have tolls (positive cost), but some might give you a refund (negative cost). You want to find the cheapest way to reach every city from your start city, even if some roads refund money.

Graph with nodes and edges:

  (A)
  / \
5/   \-3
/     \
(B)---(C)
  -2

Edges have weights: A->B=5, A->C=-3, B->C=-2

Dry Run Walkthrough

Input: Graph: A->B(5), A->C(-3), B->C(-2), start=A

Goal: Find shortest distances from A to all nodes, handling negative weights correctly

Step 1: Initialize distances: A=0, B=∞, C=∞

Distances: A=0, B=∞, C=∞

Why: Start with zero distance to start node and infinity to others

Step 2: Relax edge A->B(5): update B from ∞ to 0+5=5

Distances: A=0, B=5, C=∞

Why: Found a path to B with cost 5

Step 3: Relax edge A->C(-3): update C from ∞ to 0+(-3)=-3

Distances: A=0, B=5, C=-3

Why: Found a cheaper path to C with negative weight

Step 4: Relax edge B->C(-2): update C from -3 to 5+(-2)=3 (no update since -3 < 3)

Distances: A=0, B=5, C=-3

Why: Current path to C is already cheaper (-3), so no change

Step 5: Second iteration: Relax edge A->B(5): no update since B=5 already

Distances: A=0, B=5, C=-3

Why: No better path found to B

Step 6: Relax edge A->C(-3): no update since C=-3 already

Distances: A=0, B=5, C=-3

Why: No better path found to C

Step 7: Relax edge B->C(-2): no update since C=-3 already

Distances: A=0, B=5, C=-3

Why: No better path found to C

Step 8: No changes in this iteration, algorithm stops

Distances: A=0, B=5, C=-3

Why: Distances stabilized, shortest paths found

Result:

Distances: A=0, B=5, C=-3

Annotated Code

DSA Java

import java.util.*;

class Edge {
    int src, dest, weight;
    Edge(int s, int d, int w) {
        src = s; dest = d; weight = w;
    }
}

public class BellmanFord {
    static void bellmanFord(int vertices, List<Edge> edges, int start) {
        int[] dist = new int[vertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Relax edges repeatedly
        for (int i = 1; i < vertices; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight < dist[e.dest]) {
                    dist[e.dest] = dist[e.src] + e.weight; // update distance
                    updated = true;
                }
            }
            if (!updated) break; // no update means shortest paths found
        }

        // Check for negative weight cycles
        for (Edge e : edges) {
            if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight < dist[e.dest]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }

        // Print distances
        for (int i = 0; i < vertices; i++) {
            System.out.println("Distance from " + (char)('A' + start) + " to " + (char)('A' + i) + " is " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int vertices = 3;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 5)); // A->B
        edges.add(new Edge(0, 2, -3)); // A->C
        edges.add(new Edge(1, 2, -2)); // B->C

        bellmanFord(vertices, edges, 0); // start from A
    }
}

dist[start] = 0;

Initialize start node distance to zero

for (int i = 1; i < vertices; i++) {

Repeat relaxation for V-1 times to find shortest paths

if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight < dist[e.dest]) {

Check if current edge can improve destination distance

dist[e.dest] = dist[e.src] + e.weight;

Update distance to destination node

if (!updated) break;

Stop early if no distance updated in this iteration

for (Edge e : edges) { if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight < dist[e.dest]) {

Detect negative weight cycle if any edge can still relax

System.out.println("Distance from " + (char)('A' + start) + " to " + (char)('A' + i) + " is " + dist[i]);

Print final shortest distances

Output

Distance from A to A is 0

Distance from A to B is 5

Distance from A to C is -3

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times where V is vertices and E is edges

Space: O(V) for storing distances to each vertex

vs Alternative: Compared to Dijkstra's algorithm which is faster but cannot handle negative weights, Bellman-Ford works with negative weights but is slower

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and reports it instead of giving wrong distances

DSA Java

if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight < dist[e.dest]) { System.out.println("Graph contains negative weight cycle"); return; }

Graph with no edges

Distances remain infinity except start node which is zero

DSA Java

dist[start] = 0;

Single vertex graph

Distance to itself is zero, no edges to relax

DSA Java

dist[start] = 0;

When to Use This Pattern

When you see shortest path problems with possible negative edge weights, reach for Bellman-Ford because it handles negative weights and detects negative cycles.

Common Mistakes

Mistake: Using Dijkstra's algorithm on graphs with negative weights
Fix: Use Bellman-Ford algorithm instead because Dijkstra fails with negative weights

Mistake: Not checking for negative weight cycles
Fix: Add a final check after relaxation to detect cycles that reduce distances indefinitely

Summary

Finds shortest paths from one node to all others even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Keep relaxing edges repeatedly and stop early if no updates; detect cycles by checking for further relaxations.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It can handle graphs with negative weight edges.

B. It runs faster on all graphs.

C. It uses less memory.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand Dijkstra's limitation

   Dijkstra's algorithm cannot handle negative weight edges correctly because it assumes once a node is visited, its shortest path is finalized.

2. Step 2: Bellman-Ford's capability

   Bellman-Ford algorithm relaxes edges multiple times and can detect negative weight edges, allowing it to work correctly even with negative weights.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option A

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges, Dijkstra doesn't [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Believing it only works on acyclic graphs
• Confusing memory usage advantages

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in Java?

easy

A. int[] dist = new int[V]; Arrays.fill(dist, -1); dist[src] = 0;

B. int[] dist = new int[V]; dist[src] = Integer.MAX_VALUE;

C. int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;

D. int[] dist = new int[V]; Arrays.fill(dist, 0);

Solution

1. Step 1: Initialize distances to max value

   We set all distances to Integer.MAX_VALUE to represent infinity initially.

2. Step 2: Set source distance to zero

   The source vertex distance is set to 0 because distance from source to itself is zero.

3. Final Answer:

   int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; -> Option C

4. Quick Check:

   Distance init with max + source zero = D [OK]

Hint: Initialize all distances to max, source to zero [OK]

Common Mistakes:

• Setting source distance to max instead of zero
• Filling distances with zero instead of max
• Using -1 which is invalid for distances

3. Consider the following graph edges and weights:

int[][] edges = {
  {0, 1, 4},
  {0, 2, 5},
  {1, 2, -3},
  {2, 3, 4}
};
int V = 4; int src = 0;

What is the shortest distance array after running Bellman-Ford from source 0?

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 5]

C. [0, 4, 1, 9]

D. [0, 0, -3, 1]

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF]

2. Step 2: Relax edges V-1 times

   Iteration 1: - Edge 0->1: dist[1] = min(INF, 0+4) = 4 - Edge 0->2: dist[2] = min(INF, 0+5) = 5 - Edge 1->2: dist[2] = min(5, 4-3) = 1 - Edge 2->3: dist[3] = min(INF, 1+4) = 5 Iteration 2 and 3 do not improve distances further.

3. Final Answer:

   [0, 4, 1, 5] -> Option B

4. Quick Check:

   Relax edges 3 times, final dist = [0,4,1,5] [OK]

Hint: Relax edges V-1 times, update distances each time [OK]

Common Mistakes:

• Not updating dist[2] after edge 1->2 relaxation
• Ignoring negative edge effect
• Stopping after first iteration

4. Given this snippet of Bellman-Ford code, what is the error?

for (int i = 0; i < V; i++) {
  for (int[] edge : edges) {
    int u = edge[0], v = edge[1], w = edge[2];
    if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The outer loop should run V-1 times, not V times.

B. The condition dist[u] != Integer.MAX_VALUE is incorrect.

C. The edge array indexing is wrong.

D. The distance update should be dist[u] - w instead of dist[u] + w.

Solution

1. Step 1: Check loop iteration count

   Bellman-Ford requires relaxing edges exactly V-1 times to find shortest paths.

2. Step 2: Identify loop error

   The code runs the outer loop V times, which is one extra iteration and can cause incorrect behavior or unnecessary work.

3. Final Answer:

   The outer loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Outer loop count = V-1 [OK]

Hint: Run outer loop V-1 times for correct relaxation [OK]

Common Mistakes:

• Running loop V times instead of V-1
• Misunderstanding distance initialization condition
• Incorrect edge array indexing

5. You run Bellman-Ford on a graph with edges:

int[][] edges = {
  {0, 1, 1},
  {1, 2, -1},
  {2, 3, -1},
  {3, 1, -1}
};
int V = 4; int src = 0;

What will the algorithm detect after V-1 iterations?

hard

A. Algorithm will throw an exception due to negative weights.

B. No negative weight cycle; shortest paths found.

C. Distances will all be zero.

D. A negative weight cycle exists reachable from the source.

Solution

1. Step 1: Identify cycle in graph

   Edges 1->2, 2->3, 3->1 form a cycle with total weight -3 (negative).

2. Step 2: Bellman-Ford detects negative cycles

   After V-1 iterations, the algorithm checks for further relaxation. If possible, it means a negative weight cycle exists reachable from source.

3. Final Answer:

   A negative weight cycle exists reachable from the source. -> Option D

4. Quick Check:

   Negative cycle detected = C [OK]

Hint: Check for extra relaxation after V-1 iterations to find negative cycles [OK]

Common Mistakes:

• Assuming no negative cycle despite cycle with negative sum
• Expecting exception on negative weights
• Thinking distances become zero automatically