Bellman Ford Algorithm Negative Weights in DSA Go - Time & Space Complexity

Time Complexity: Bellman Ford Algorithm Negative Weights

O(V * E)

Understanding Time Complexity

We want to understand how the Bellman Ford algorithm's running time changes as the graph size grows.

Specifically, how does the number of edges and vertices affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func BellmanFord(edges [][]int, V int, src int) []int {
    dist := make([]int, V)
    for i := range dist {
        dist[i] = 1<<31 - 1 // infinity
    }
    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<<31-1 && dist[u]+w < dist[v] {
                dist[v] = dist[u] + w
            }
        }
    }
    return dist
}
    

This code finds shortest paths from a source to all vertices, even with negative weights, by relaxing edges repeatedly.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop that goes through all edges to update distances.
• How many times: This inner loop runs once for each vertex minus one, so (V-1) times.

How Execution Grows With Input

Each vertex causes the algorithm to check all edges once, so the total work grows with both vertices and edges.

Input Size (V, E)	Approx. Operations
V=10, E=20	About 9 * 20 = 180 checks
V=100, E=200	About 99 * 200 = 19,800 checks
V=1000, E=2000	About 999 * 2000 = 1,998,000 checks

Pattern observation: The work grows roughly by multiplying the number of vertices and edges.

Final Time Complexity

Time Complexity: O(V * E)

This means the time needed grows proportionally to the number of vertices times the number of edges.

Common Mistake

[X] Wrong: "The algorithm runs in O(E) time because it just loops over edges."

[OK] Correct: The edge loop runs multiple times--once for each vertex minus one--so total work depends on both vertices and edges.

Interview Connect

Understanding this time complexity helps you explain why Bellman Ford is slower than other shortest path algorithms but necessary for graphs with negative weights.

Self-Check

"What if we stopped the algorithm early when no distances change in an iteration? How would the time complexity change?"

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