Bellman Ford Algorithm Negative Weights in DSA Go - 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 this graph from source vertex 0?

DSA Go

package main
import "fmt"

func bellmanFord(edges [][]int, V, src int) []int {
    dist := make([]int, V)
    for i := range dist {
        dist[i] = 1 << 30
    }
    dist[src] = 0

    for i := 0; i < V-1; i++ {
        for _, edge := range edges {
            u, v, w := edge[0], edge[1], edge[2]
            if dist[u] != 1<<30 && dist[u]+w < dist[v] {
                dist[v] = dist[u] + w
            }
        }
    }
    return dist
}

func main() {
    edges := [][]int{
        {0, 1, 4},
        {0, 2, 5},
        {1, 2, -3},
        {2, 3, 4},
        {3, 1, -6},
    }
    dist := bellmanFord(edges, 4, 0)
    fmt.Println(dist)
}

A [0, 1, -2, 2]

B [0, -2, -1, 3]

C [0, 4, 1, 5]

D [0, 4, 1, -1]

💡 Hint

Trace the relaxation steps carefully, especially the negative edges.

The Bellman-Ford algorithm relaxes edges V-1 times. Negative edges reduce distances step by step. After all relaxations, the shortest distances from source 0 are [0, 1, -2, 2].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

Which statement correctly describes how Bellman-Ford detects a negative weight cycle?

A If the source vertex distance changes after the first iteration, a negative weight cycle exists.

B If after V-1 iterations, any edge can still be relaxed, a negative weight cycle exists.

C If the distance to any vertex becomes zero, a negative weight cycle exists.

D If all edges are relaxed exactly once, there is a negative weight cycle.

💡 Hint

Think about what happens if distances keep decreasing after expected iterations.

Bellman-Ford runs V-1 iterations to relax edges. If any edge can still be relaxed after that, it means a cycle reduces distances indefinitely, indicating a negative weight cycle.

🔧 Debug

advanced

Identify the error in this Bellman-Ford implementation snippet

What error will this code produce when run?

DSA Go

dist := make([]int, V)
for i := 0; i <= V; i++ {
    dist[i] = 1 << 30
}
dist[src] = 0

A Compilation error due to missing import

B No error, runs correctly

C Index out of range error

D Logical error: distances not initialized

💡 Hint

Check the loop boundary compared to slice length.

The loop runs from 0 to V inclusive, but the slice has length V, so index V is out of range causing runtime panic.

🚀 Application

advanced

Using Bellman-Ford to find shortest paths in a graph with negative edges

Given the edges and vertices below, what is the shortest path distance from vertex 0 to vertex 4 after running Bellman-Ford?

DSA Go

edges := [][]int{
    {0, 1, 6},
    {0, 2, 7},
    {1, 2, 8},
    {1, 3, 5},
    {1, 4, -4},
    {2, 3, -3},
    {2, 4, 9},
    {3, 1, -2},
    {4, 3, 7},
}
V := 5
src := 0
// Bellman-Ford run here

A -2

B 0

C 1

D 2

💡 Hint

Consider the negative edges and cycles carefully.

The shortest path from 0 to 4 is 0 -> 1 -> 4 with total weight 6 + (-4) = 2, but better path is 0 -> 2 -> 3 -> 1 -> 4 with weight 7 + (-3) + (-2) + (-4) = -2.

❓ Predict Output

expert

Output after detecting negative cycle with Bellman-Ford

What will the program print after running Bellman-Ford on this graph with a negative cycle?

DSA Go

package main
import "fmt"

func bellmanFord(edges [][]int, V, src int) (bool, []int) {
    dist := make([]int, V)
    for i := range dist {
        dist[i] = 1 << 30
    }
    dist[src] = 0

    for i := 0; i < V-1; i++ {
        for _, edge := range edges {
            u, v, w := edge[0], edge[1], edge[2]
            if dist[u] != 1<<30 && dist[u]+w < dist[v] {
                dist[v] = dist[u] + w
            }
        }
    }

    for _, edge := range edges {
        u, v, w := edge[0], edge[1], edge[2]
        if dist[u] != 1<<30 && dist[u]+w < dist[v] {
            return false, dist
        }
    }
    return true, dist
}

func main() {
    edges := [][]int{
        {0, 1, 1},
        {1, 2, -1},
        {2, 3, -1},
        {3, 1, -1},
    }
    ok, dist := bellmanFord(edges, 4, 0)
    if !ok {
        fmt.Println("Negative cycle detected")
    } else {
        fmt.Println(dist)
    }
}

A [0, 1, 0, -1]

B Compilation error

C [0, 1, 2, 3]

D Negative cycle detected

💡 Hint

Check the final cycle detection loop.

The graph contains a negative cycle (1 -> 2 -> 3 -> 1). The algorithm detects it and returns false, so the program prints "Negative cycle detected".

Practice

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

easy

A. It runs faster on all graphs.

B. It uses less memory.

C. It can handle graphs with negative weight edges.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand Dijkstra's limitation

   Dijkstra's algorithm cannot handle negative weight edges because it assumes once a node is visited with the shortest path, it won't be updated again.

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 C

4. Quick Check:

   Negative weights handled = B [OK]

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

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Believing it uses less memory than Dijkstra
• Assuming it only works on acyclic graphs

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

easy

A. dist := make([]int, V); for i := range dist { dist[i] = math.MaxInt32 }

B. dist := make([]int, V); for i := range dist { dist[i] = 0 }

C. dist := make([]int, V); for i := range dist { dist[i] = -1 }

D. dist := make([]int, V); for i := range dist { dist[i] = 1 }

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity) to represent unknown distance.

2. Step 2: Use math.MaxInt32 for infinity

   In Go, math.MaxInt32 is used to represent a large integer value for initialization.

3. Final Answer:

   dist := make([]int, V); for i := range dist { dist[i] = math.MaxInt32 } -> Option A

4. Quick Check:

   Initialize distances to max int = A [OK]

Hint: Initialize distances to max int except source [OK]

Common Mistakes:

• Initializing distances to zero
• Using negative values for distances
• Not initializing distances at all

3. What will be the output distances array after running Bellman-Ford on this graph with edges:
edges = []Edge{{0,1,4}, {0,2,5}, {1,2,-3}, {2,3,4}} starting from source 0?

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 5]

C. [0, 4, 1, 9]

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

Solution

1. Step 1: Initialize distances

   dist = [0, ∞, ∞, ∞]

2. Step 2: Relax edges repeatedly

   After first relaxation: dist[1]=4, dist[2]=5
   After second relaxation: dist[2]=min(5,4 + (-3))=1
   After third relaxation: dist[3]=dist[2] + 4 = 1 + 4 = 5
   After further relaxations no changes occur.

3. Final Answer:

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

4. Quick Check:

   Relax edges stepwise = A [OK]

Hint: Relax edges V-1 times to update distances [OK]

Common Mistakes:

• Not updating dist[2] after negative edge relaxation
• Adding weights incorrectly
• Confusing edge directions

4. Identify the bug in this Go code snippet for Bellman-Ford algorithm:

for i := 0; i < V; i++ {
  for _, e := range edges {
    if dist[e.src] + e.weight < dist[e.dest] {
      dist[e.dest] = dist[e.src] + e.weight
    }
  }
}

medium

A. Loop should run V-1 times, not V times.

B. The condition should use <= instead of <.

C. dist array is not initialized.

D. Edges should be relaxed only once.

Solution

1. Step 1: Check loop iteration count

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

2. Step 2: Identify off-by-one error

   The loop runs V times, which is one extra iteration and may cause incorrect behavior or unnecessary work.

3. Final Answer:

   Loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Relax edges V-1 times = A [OK]

Hint: Relax edges exactly V-1 times [OK]

Common Mistakes:

• Running loop V times instead of V-1
• Using wrong comparison operator
• Not initializing dist array

5. Given a graph with edges:
edges = []Edge{{0,1,1}, {1,2,-1}, {2,3,-1}, {3,1,-1}}
and source vertex 0, what does Bellman-Ford detect after running?

hard

A. No negative cycle detected; shortest paths found.

B. Distances remain infinite for all vertices except source.

C. Algorithm fails due to zero-weight edges.

D. Negative weight cycle detected involving vertices 1, 2, 3.

Solution

1. Step 1: Analyze edges for cycles

   The edges form a cycle 1 -> 2 -> 3 -> 1 with total weight -3 (negative cycle).

2. Step 2: Bellman-Ford cycle detection

   After V-1 relaxations, one more relaxation detects if any distance can still be reduced, indicating a negative cycle.

3. Final Answer:

   Negative weight cycle detected involving vertices 1, 2, 3. -> Option D

4. Quick Check:

   Negative cycle detection = D [OK]

Hint: Check for distance updates after V-1 relaxations [OK]

Common Mistakes:

• Ignoring negative cycles
• Assuming zero-weight edges cause failure
• Thinking no cycle exists