Bellman Ford Algorithm Negative Weights in DSA Go

Mental Model

Bellman Ford finds shortest paths even if edges have negative weights by relaxing edges repeatedly.

Analogy: Imagine you want to find the cheapest route between cities, but some roads give discounts (negative cost). You check all roads multiple times to update your best guess for the cheapest path.

Graph:
  (A)
  /  \
5/    \-3
 /      \
(B)---->(C)
    2

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

Dry Run Walkthrough

Input: Graph with edges: A->B=5, A->C=-3, B->C=2; start vertex A

Goal: Find shortest distances from A to all vertices, handling negative edge weight

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

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

Why: Start with zero distance to source and infinity to others

Step 2: Relax edge A->B: 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: 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: check if C can be improved from -3 to 5+2=7 (no update)

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

Why: Current path to C is already cheaper

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

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

Why: No better path found

Step 6: Second iteration: Relax edge A->C (no update, C=-3)

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

Why: No better path found

Step 7: Second iteration: Relax edge B->C (no update, C=-3)

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

Why: No better path found

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	from, to, weight int
}

func bellmanFord(edges []Edge, vertices int, start int) ([]int, bool) {
	dist := make([]int, vertices)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	// Relax edges repeatedly
	for i := 0; i < vertices-1; i++ {
		updated := false
		for _, e := range edges {
			if dist[e.from] != math.MaxInt32 && dist[e.from]+e.weight < dist[e.to] {
				dist[e.to] = dist[e.from] + e.weight
				updated = true
			}
		}
		if !updated {
			break
		}
	}

	// Check for negative weight cycles
	for _, e := range edges {
		if dist[e.from] != math.MaxInt32 && dist[e.from]+e.weight < dist[e.to] {
			return dist, false // Negative cycle detected
		}
	}

	return dist, true
}

func main() {
	// Vertices: A=0, B=1, C=2
	edges := []Edge{
		{0, 1, 5},
		{0, 2, -3},
		{1, 2, 2},
	}
	dist, ok := bellmanFord(edges, 3, 0)
	if !ok {
		fmt.Println("Graph contains a negative weight cycle")
		return
	}
	for i, d := range dist {
		fmt.Printf("Distance from A to %c: %d\n", 'A'+i, d)
	}
}

dist[start] = 0

Set distance to start vertex as zero

for i := 0; i < vertices-1; i++ {

Repeat relaxation for all vertices minus one times

if dist[e.from] != math.MaxInt32 && dist[e.from]+e.weight < dist[e.to] {

Check if current edge can improve distance to destination

dist[e.to] = dist[e.from] + e.weight

Update distance to destination vertex

if !updated { break }

Stop early if no updates in this iteration

for _, e := range edges { if dist[e.from] != math.MaxInt32 && dist[e.from]+e.weight < dist[e.to] { return dist, false } }

Detect negative weight cycle by checking for further improvements

Output

Distance from A to A: 0

Distance from A to B: 5

Distance from A to C: -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: Unlike Dijkstra which fails with negative weights, Bellman Ford handles them but is slower due to repeated edge checks

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and returns false indicating no valid shortest path

DSA Go

for _, e := range edges { if dist[e.from] != math.MaxInt32 && dist[e.from]+e.weight < dist[e.to] { return dist, false } }

Graph with no edges

Distances remain infinity except start vertex which is zero

DSA Go

dist[start] = 0

Single vertex graph

Distance to itself is zero, no edges to relax

DSA Go

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 can handle negative weights and detect negative cycles.

Common Mistakes

Mistake: Using Dijkstra's algorithm on graphs with negative weights
Fix: Use Bellman Ford algorithm instead as it correctly handles negative weights

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final check for further distance improvements to detect negative cycles

Summary

Finds shortest paths from a start vertex even when edges have negative weights.

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

Repeatedly relax all edges to update shortest paths and detect cycles.

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