Bellman Ford Algorithm Negative Weights in DSA Java - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest path from a starting city to all other cities. Some roads have toll discounts, which means the cost can be negative. You will use the Bellman Ford algorithm to handle these negative weights safely.

🎯 Goal: Build a Java program that uses the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities in a graph with possible negative edge weights.

📋 What You'll Learn

Create a graph using an edge list with exact edges and weights

Set up a distance array with initial values

Implement the Bellman Ford relaxation steps exactly

Print the final shortest distances from the start city

💡 Why This Matters

🌍 Real World

Navigation systems and routing algorithms often need to handle roads with discounts or penalties, which can be modeled as negative weights.

💼 Career

Understanding Bellman Ford is important for software engineers working on graph algorithms, network routing, and optimization problems.

1

Create the graph edges

Create an array of edges called edges with these exact entries: new int[]{0, 1, 4}, new int[]{0, 2, 5}, new int[]{1, 2, -3}, new int[]{2, 3, 4}, new int[]{3, 1, 6}.

DSA Java

// Create the edges array with given edges
// Your code here

Hint

Use a 2D int array named edges where each inner array has three integers: source, destination, and weight.

2

Initialize the distances array

Create an int array called distances of size 4 and set all values to Integer.MAX_VALUE except distances[0] which should be 0.

DSA Java

int[][] edges = {
    new int[]{0, 1, 4},
    new int[]{0, 2, 5},
    new int[]{1, 2, -3},
    new int[]{2, 3, 4},
    new int[]{3, 1, 6}
};
// Initialize distances array with size 4
// Your code here

Hint

Use a for loop to set all distances to Integer.MAX_VALUE except the start city at index 0.

3

Implement Bellman Ford relaxation

Write a nested loop where the outer loop runs 3 times and the inner loop iterates over edges. Inside the inner loop, if distances[edge[0]] is not Integer.MAX_VALUE and distances[edge[0]] + edge[2] < distances[edge[1]], update distances[edge[1]] to distances[edge[0]] + edge[2].

DSA Java

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

int[] distances = new int[4];
for (int i = 0; i < 4; i++) {
    distances[i] = Integer.MAX_VALUE;
}
distances[0] = 0;

// Implement Bellman Ford relaxation loops
// Your code here

Hint

Use two loops: outer loop runs 3 times (number of vertices - 1), inner loop goes through each edge to relax distances.

4

Print the shortest distances

Use a for loop with variable i from 0 to 3 to print each element of distances on a new line using System.out.println(distances[i]).

DSA Java

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

int[] distances = new int[4];
for (int i = 0; i < 4; i++) {
    distances[i] = Integer.MAX_VALUE;
}
distances[0] = 0;

for (int i = 0; i < 3; i++) {
    for (int[] edge : edges) {
        int src = edge[0];
        int dest = edge[1];
        int weight = edge[2];
        if (distances[src] != Integer.MAX_VALUE && distances[src] + weight < distances[dest]) {
            distances[dest] = distances[src] + weight;
        }
    }
}

// Print all distances
// Your code here

Hint

Use a for loop to print each distance on its own line using System.out.println.

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