Bellman Ford Algorithm Negative Weights in DSA Python - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances

↓

Repeat V-1 times

→For each edge

↓

Update distance

↓

Check for negative cycle

↓

Output shortest distances or negative cycle warning

Start with distances set to infinity except source. Relax all edges V-1 times to find shortest paths. Then check for negative cycles.

Execution Sample

DSA Python

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,4),(3,1,6)]
V = 4
dist = [0,float('inf'),float('inf'),float('inf')]
for _ in range(V-1):
  for u,v,w in edges:
    if dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
# Check for negative weight cycles
for u,v,w in edges:
  if dist[u] + w < dist[v]:
    print('Graph contains a negative weight cycle')

This code runs Bellman-Ford on a graph with 4 vertices and edges with negative weights to find shortest distances from vertex 0.

Execution Table

Step	Operation	Edge Relaxed	Distance Before	Distance After	Visual State
1	Initialize distances	-	[0, inf, inf, inf]	[0, inf, inf, inf]	0 -> 0, 1 -> ∞, 2 -> ∞, 3 -> ∞
2	Relax edge	(0->1,4)	[0, inf, inf, inf]	[0, 4, inf, inf]	0 -> 0, 1 -> 4, 2 -> ∞, 3 -> ∞
3	Relax edge	(0->2,5)	[0, 4, inf, inf]	[0, 4, 5, inf]	0 -> 0, 1 -> 4, 2 -> 5, 3 -> ∞
4	Relax edge	(1->2,-3)	[0, 4, 5, inf]	[0, 4, 1, inf]	0 -> 0, 1 -> 4, 2 -> 1, 3 -> ∞
5	Relax edge	(2->3,4)	[0, 4, 1, inf]	[0, 4, 1, 5]	0 -> 0, 1 -> 4, 2 -> 1, 3 -> 5
6	Relax edge	(3->1,6)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
7	Relax edge	(0->1,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
8	Relax edge	(0->2,5)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
9	Relax edge	(1->2,-3)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
10	Relax edge	(2->3,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
11	Relax edge	(3->1,6)	[0, 4, 1, 5]	[0, 4, 1, 5]	No change
12	Check negative cycle	-	[0, 4, 1, 5]	[0, 4, 1, 5]	No negative cycle detected

💡 After V-1=3 iterations, no distance updates in last iteration means shortest paths found; no negative cycle.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
dist	[0, ∞, ∞, ∞]	[0, 4, 1, 5]	[0, 4, 1, 5]	[0, 4, 1, 5]	[0, 4, 1, 5]

Key Moments - 3 Insights

Why do we relax edges V-1 times?

Because the longest possible path without cycles has V-1 edges. Relaxing that many times ensures shortest paths are found (see execution_table rows 2-11).

What happens if distances don't change in an iteration?

It means shortest paths are stable and no further updates are needed. The algorithm can stop early (see execution_table rows 7-11).

How does the algorithm detect negative weight cycles?

After V-1 relaxations, if any edge can still be relaxed (distance updated), a negative cycle exists (see execution_table row 12).

Visual Quiz - 3 Questions

Look at the execution_table, what is the distance to vertex 2 after the first iteration?

A [0, 4, ∞, ∞]

B [0, 4, 1, 5]

C [0, ∞, ∞, ∞]

D [0, 4, 5, ∞]

💡 Hint

Check execution_table row 5 for distance updates after first iteration.

At which step does the distance to vertex 3 first get updated?

A Step 4

B Step 6

C Step 5

D Step 3

💡 Hint

Look at execution_table rows showing distance changes to vertex 3.

If the edge (3->1,6) had weight -10 instead, what would happen in the last iteration?

A Distance to vertex 1 would decrease, indicating a negative cycle

B No change in distances

C Algorithm would stop early

D Distance to vertex 3 would increase

💡 Hint

Check how relaxing edges after V-1 iterations detects negative cycles (execution_table row 12).

Concept Snapshot

Bellman-Ford Algorithm:
- Initialize distances: source=0, others=∞
- Relax all edges V-1 times
- Update distance if shorter path found
- Check for negative cycles by one more relaxation
- Detects negative weights unlike Dijkstra
- Stops if no updates in an iteration

Full Transcript

Bellman-Ford algorithm finds shortest paths from a source vertex to all others even with negative edge weights. It starts by setting distances to infinity except the source which is zero. Then it repeats relaxing all edges V-1 times, where V is the number of vertices. Relaxing means updating the distance to a vertex if a shorter path is found through an edge. After these iterations, it checks for negative weight cycles by trying to relax edges once more. If any distance updates, a negative cycle exists. The execution table shows step-by-step how distances change after relaxing each edge. The variable tracker records the distance array after each iteration. Key moments clarify why V-1 iterations are needed, what stable distances mean, and how negative cycles are detected. The visual quiz tests understanding of distance updates and cycle detection. The snapshot summarizes the algorithm's key points for quick recall.

Practice

1. What is the main purpose of the Bellman-Ford algorithm when dealing with graphs that have negative edge weights?

easy

A. To sort vertices in topological order

B. To find the longest path in a graph

C. To detect cycles in an undirected graph

D. To find the shortest path from a single source to all vertices, even with negative weights

Solution

1. Step 1: Understand Bellman-Ford's goal

   The Bellman-Ford algorithm is designed to find shortest paths from one source vertex to all other vertices in a graph, even if some edges have negative weights.

2. Step 2: Compare with other algorithms

   Unlike Dijkstra's algorithm, Bellman-Ford can handle negative weights and also detect negative weight cycles.

3. Final Answer:

   To find the shortest path from a single source to all vertices, even with negative weights -> Option D

4. Quick Check:

   Bellman-Ford finds shortest paths with negative weights [OK]

Hint: Bellman-Ford handles negative edges for shortest paths [OK]

Common Mistakes:

• Confusing Bellman-Ford with Dijkstra's algorithm
• Thinking it finds longest paths
• Assuming it only detects cycles

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in Python for a graph with vertices numbered 0 to n-1 and source vertex src?

easy

A. dist = [float('inf')] * n; dist[src] = 0

B. dist = [0] * n; dist[src] = float('inf')

C. dist = [null] * n; dist[src] = 0

D. dist = [float('inf')] * n; dist[0] = 0

Solution

1. Step 1: Initialize distances to infinity

   We set all distances to infinity to represent unknown paths initially.

2. Step 2: Set source distance to zero

   The distance from the source vertex to itself is zero, so dist[src] = 0.

3. Final Answer:

   dist = [float('inf')] * n; dist[src] = 0 -> Option A

4. Quick Check:

   Initialize all to infinity, source to zero [OK]

Hint: Set all distances to infinity, source to zero [OK]

Common Mistakes:

• Setting all distances to zero
• Setting source distance to infinity
• Using null instead of infinity

3. What will be the output distances array after running Bellman-Ford on the following graph with source vertex 0? Edges: [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)]

n = 4
edges = [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)]
src = 0

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 9]

C. [0, 4, 1, 5]

D. [0, 5, 2, 6]

Solution

1. Step 1: Initialize distances

   dist = [0, inf, inf, inf]

2. Step 2: Relax edges repeatedly

   Iteration 1: dist[1] = 4, dist[2] = 5; then dist[2] = min(5, 4 + (-3)) = 1; dist[3] = dist[2] + 4 = 5 Iteration 2: No further updates

3. Final Answer:

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

4. Quick Check:

   Relax edges 3 times, get distances [0,4,1,5] [OK]

Hint: Relax edges n-1 times, update distances [OK]

Common Mistakes:

• Not updating dist[2] with negative edge
• Calculating dist[3] incorrectly
• Stopping relaxation too early

4. Consider the following code snippet for Bellman-Ford. What is the error?

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

medium

A. The outer loop should run n-1 times, not n times

B. The distance initialization is incorrect

C. The edge relaxation condition is wrong

D. The function does not return the path, only distances

Solution

1. Step 1: Check loop iterations

   Bellman-Ford requires relaxing edges exactly n-1 times to guarantee shortest paths.

2. Step 2: Identify the error

   The code runs the outer loop n times, which is one extra iteration and can cause incorrect detection of negative cycles or unnecessary work.

3. Final Answer:

   The outer loop should run n-1 times, not n times -> Option A

4. Quick Check:

   Outer loop runs n-1 times [OK]

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

Common Mistakes:

• Running outer loop n times instead of n-1
• Misinitializing distances
• Confusing relaxation condition

5. Given a graph with edges [(0,1,1), (1,2,-1), (2,0,-1)], what will Bellman-Ford detect when run from source 0, and why?

hard

A. It will return infinite distances for all vertices

B. It will detect a negative weight cycle because the cycle sum is negative

C. It will raise an error due to invalid edges

D. It will find shortest paths without issues

Solution

1. Step 1: Calculate cycle weight sum

   The cycle is 0->1->2->0 with weights 1 + (-1) + (-1) = -1, which is negative.

2. Step 2: Understand Bellman-Ford behavior

   Bellman-Ford detects negative weight cycles by checking for further relaxation after n-1 iterations.

3. Step 3: Conclusion

   Since the cycle sum is negative, Bellman-Ford will detect this negative weight cycle.

4. Final Answer:

   It will detect a negative weight cycle because the cycle sum is negative -> Option B

5. Quick Check:

   Negative cycle sum triggers detection [OK]

Hint: Negative cycle sum means Bellman-Ford detects cycle [OK]

Common Mistakes:

• Assuming no negative cycles exist
• Thinking algorithm crashes on negative cycles
• Confusing cycle detection with path finding