Bellman Ford Algorithm Negative Weights in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bellman-Ford on a graph with negative edges

What is the shortest distance array output after running Bellman-Ford on the given graph from source vertex 0?

DSA Java

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

public class BellmanFord {
    static int V = 4;
    static int E = 5;
    static Edge[] edges = new Edge[E];

    public static void main(String[] args) {
        edges[0] = new Edge(0, 1, 1);
        edges[1] = new Edge(0, 2, 4);
        edges[2] = new Edge(1, 2, -3);
        edges[3] = new Edge(1, 3, 2);
        edges[4] = new Edge(3, 2, 5);

        int[] dist = new int[V];
        for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE;
        dist[0] = 0;

        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].src;
                int v = edges[j].dest;
                int w = edges[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        System.out.print("[" + dist[0]);
        for (int i = 1; i < V; i++) {
            System.out.print(", " + dist[i]);
        }
        System.out.println("]");
    }
}

A [0, 1, -2, 3]

B [0, 1, 4, 3]

C [0, 1, -3, 2]

D [0, 1, -2, 2]

💡 Hint

Remember Bellman-Ford relaxes edges V-1 times and updates distances if a shorter path is found.

The algorithm updates distances by relaxing edges. The negative edge from 1 to 2 reduces distance to 2 to -2 after iterations.

❓ Predict Output

intermediate

Detecting negative weight cycle output

What will the program print when detecting a negative weight cycle in the graph?

DSA Java

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

public class BellmanFordCycle {
    static int V = 3;
    static int E = 3;
    static Edge[] edges = new Edge[E];

    public static void main(String[] args) {
        edges[0] = new Edge(0, 1, 1);
        edges[1] = new Edge(1, 2, -1);
        edges[2] = new Edge(2, 0, -1);

        int[] dist = new int[V];
        for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE;
        dist[0] = 0;

        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].src;
                int v = edges[j].dest;
                int w = edges[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        boolean hasNegativeCycle = false;
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                hasNegativeCycle = true;
                break;
            }
        }

        if (hasNegativeCycle) {
            System.out.println("Negative cycle detected");
        } else {
            System.out.println("No negative cycle");
        }
    }
}

A Infinite loop

B Negative cycle detected

C ArrayIndexOutOfBoundsException

D No negative cycle

💡 Hint

Check if any edge can still relax after V-1 iterations.

The cycle 0->1->2->0 has total negative weight, so the algorithm detects a negative cycle.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path

Why does the following Bellman-Ford implementation produce incorrect shortest paths when negative edges exist?

DSA Java

int V = 3;
int E = 3;
Edge[] edges = new Edge[E];

// edges initialization omitted for brevity

int[] dist = new int[V];
for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE;
dist[0] = 0;

for (int i = 0; i < V; i++) {  // Loop runs V times instead of V-1
    for (int j = 0; j < E; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int w = edges[j].weight;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}

A The weight comparison uses <= instead of <

B The distance array is not initialized to zero

C Edges are not relaxed in reverse order

D The outer loop should run V-1 times, not V times

💡 Hint

Bellman-Ford requires exactly V-1 iterations to guarantee shortest paths without negative cycles.

Running the loop V times can cause incorrect updates or false detection of negative cycles.

🚀 Application

advanced

Choosing Bellman-Ford over Dijkstra

Which scenario best justifies using Bellman-Ford algorithm instead of Dijkstra's algorithm?

A Graph has negative weight edges but no negative cycles

B Graph is dense with only positive weights

C Graph has no edges

D Graph has only non-negative weights and is very large

💡 Hint

Dijkstra fails with negative weights; Bellman-Ford handles them safely.

Bellman-Ford works correctly with negative weights and detects negative cycles, unlike Dijkstra.

🧠 Conceptual

expert

Effect of negative weight cycles on shortest path results

What is the effect of a negative weight cycle reachable from the source vertex on the shortest path results computed by Bellman-Ford?

A Shortest path distances remain correct but take longer to compute

B Algorithm returns the longest path distances instead

C Shortest path distances become undefined as they can decrease indefinitely

D Algorithm ignores the cycle and returns shortest paths ignoring it

💡 Hint

Think about what happens if you keep going around a negative cycle.

Negative cycles allow infinite reduction of path cost, so shortest paths are not well-defined.

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