Bellman Ford Algorithm Negative Weights in DSA Go - 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, represented as negative weights. You will implement the Bellman Ford algorithm to handle these negative weights safely.

🎯 Goal: Build a Go program that uses the Bellman Ford algorithm to find the shortest distances from a start node to all other nodes in a graph with possible negative edge weights.

📋 What You'll Learn

Create a graph as a slice of edges with exact values

Define the number of vertices and the start vertex

Implement the Bellman Ford algorithm to update distances

Print the shortest distances or detect a negative weight cycle

💡 Why This Matters

🌍 Real World

Navigation systems and network routing often need to handle negative weights like discounts or penalties safely.

💼 Career

Understanding Bellman Ford is important for roles in software engineering, especially in fields like networking, logistics, and optimization.

1

Create the graph edges

Create a slice called edges of type Edge with these exact edges: {from: 0, to: 1, weight: 6}, {from: 0, to: 2, weight: 7}, {from: 1, to: 2, weight: 8}, {from: 1, to: 3, weight: 5}, {from: 1, to: 4, weight: -4}, {from: 2, to: 3, weight: -3}, {from: 2, to: 4, weight: 9}, {from: 3, to: 1, weight: -2}, {from: 4, to: 0, weight: 2}, {from: 4, to: 3, weight: 7}.

DSA Go

package main

type Edge struct {
    from, to, weight int
}

func main() {
    // Create the edges slice with given edges
    // Your code here
}

Hint

Define edges as a slice of Edge structs with the exact edges listed.

2

Set number of vertices and start vertex

Create two variables: vertices set to 5 and start set to 0.

DSA Go

package main

type Edge struct {
    from, to, weight int
}

func main() {
    edges := []Edge{
        {from: 0, to: 1, weight: 6},
        {from: 0, to: 2, weight: 7},
        {from: 1, to: 2, weight: 8},
        {from: 1, to: 3, weight: 5},
        {from: 1, to: 4, weight: -4},
        {from: 2, to: 3, weight: -3},
        {from: 2, to: 4, weight: 9},
        {from: 3, to: 1, weight: -2},
        {from: 4, to: 0, weight: 2},
        {from: 4, to: 3, weight: 7},
    }
    // Define vertices and start variables
    // Your code here
}

Hint

Set vertices to 5 and start to 0 exactly as variables.

3

Implement Bellman Ford algorithm

Create a slice dist of length vertices with all values set to 1<<31 - 1 except dist[start] set to 0. Then run a loop from 0 to vertices-1 and inside it, loop over edges to relax edges by updating dist[edge.to] if dist[edge.from] + edge.weight < dist[edge.to].

DSA Go

package main

type Edge struct {
    from, to, weight int
}

func main() {
    edges := []Edge{
        {from: 0, to: 1, weight: 6},
        {from: 0, to: 2, weight: 7},
        {from: 1, to: 2, weight: 8},
        {from: 1, to: 3, weight: 5},
        {from: 1, to: 4, weight: -4},
        {from: 2, to: 3, weight: -3},
        {from: 2, to: 4, weight: 9},
        {from: 3, to: 1, weight: -2},
        {from: 4, to: 0, weight: 2},
        {from: 4, to: 3, weight: 7},
    }
    vertices := 5
    start := 0

    // Initialize dist slice and run Bellman Ford relaxation
    // Your code here
}

Hint

Initialize dist with max int values except start at 0. Use two nested loops: outer for vertices-1 times, inner over edges to relax distances.

4

Print shortest distances or detect negative cycle

Add a loop over edges to check if any edge can still relax distances. If yes, print "Graph contains a negative weight cycle". Otherwise, print "Vertex X: Distance Y" for each vertex X and its distance Y in dist.

DSA Go

package main

type Edge struct {
    from, to, weight int
}

func main() {
    edges := []Edge{
        {from: 0, to: 1, weight: 6},
        {from: 0, to: 2, weight: 7},
        {from: 1, to: 2, weight: 8},
        {from: 1, to: 3, weight: 5},
        {from: 1, to: 4, weight: -4},
        {from: 2, to: 3, weight: -3},
        {from: 2, to: 4, weight: 9},
        {from: 3, to: 1, weight: -2},
        {from: 4, to: 0, weight: 2},
        {from: 4, to: 3, weight: 7},
    }
    vertices := 5
    start := 0

    dist := make([]int, vertices)
    for i := 0; i < vertices; i++ {
        dist[i] = 1<<31 - 1
    }
    dist[start] = 0

    for i := 0; i < vertices-1; i++ {
        for _, edge := range edges {
            if dist[edge.from] != 1<<31-1 && dist[edge.from]+edge.weight < dist[edge.to] {
                dist[edge.to] = dist[edge.from] + edge.weight
            }
        }
    }

    // Check for negative weight cycle and print distances
    // Your code here
}

Hint

After relaxation, check again for any edge that can reduce distance to detect negative cycles. If none, print distances for each vertex.

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