Bellman-Ford algorithm in Data Structures Theory - Step-by-Step Execution

Concept Flow - Bellman-Ford algorithm

Initialize distances

↓

Repeat for V-1 times

↓

For each edge (u,v)

↓

Relax edge: if dist[u

↓

Update dist[v

↓

Check for negative cycles

↓

If found: report negative cycle

↓

Else: shortest paths ready

The algorithm initializes distances, relaxes all edges repeatedly, then checks for negative cycles to find shortest paths.

Execution Sample

Data Structures Theory

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 i in range(V-1):
  for u,v,w in edges:
    if dist[u]+w < dist[v]:
      dist[v] = dist[u]+w

This code runs Bellman-Ford on a graph with 4 vertices and 5 edges, updating shortest distances step-by-step.

Analysis Table

Step	Operation	Edge (u->v)	dist before	Check dist[u]+w < dist[v]	dist after	Notes
1.1	Relax edge	(0->1,4)	[0,∞,∞,∞]	0+4 < ∞ → True	[0,4,∞,∞]	Update dist[1]
1.2	Relax edge	(0->2,5)	[0,4,∞,∞]	0+5 < ∞ → True	[0,4,5,∞]	Update dist[2]
1.3	Relax edge	(1->2,-3)	[0,4,5,∞]	4-3 < 5 → True	[0,4,1,∞]	Update dist[2]
1.4	Relax edge	(2->3,4)	[0,4,1,∞]	1+4 < ∞ → True	[0,4,1,5]	Update dist[3]
1.5	Relax edge	(3->1,6)	[0,4,1,5]	5+6 < 4 → False	[0,4,1,5]	No update
2.1	Relax edge	(0->1,4)	[0,4,1,5]	0+4 < 4 → False	[0,4,1,5]	No update
2.2	Relax edge	(0->2,5)	[0,4,1,5]	0+5 < 1 → False	[0,4,1,5]	No update
2.3	Relax edge	(1->2,-3)	[0,4,1,5]	4-3 < 1 → False	[0,4,1,5]	No update
2.4	Relax edge	(2->3,4)	[0,4,1,5]	1+4 < 5 → False	[0,4,1,5]	No update
2.5	Relax edge	(3->1,6)	[0,4,1,5]	5+6 < 4 → False	[0,4,1,5]	No update
3.1	Relax edge	(0->1,4)	[0,4,1,5]	0+4 < 4 → False	[0,4,1,5]	No update
3.2	Relax edge	(0->2,5)	[0,4,1,5]	0+5 < 1 → False	[0,4,1,5]	No update
3.3	Relax edge	(1->2,-3)	[0,4,1,5]	4-3 < 1 → False	[0,4,1,5]	No update
3.4	Relax edge	(2->3,4)	[0,4,1,5]	1+4 < 5 → False	[0,4,1,5]	No update
3.5	Relax edge	(3->1,6)	[0,4,1,5]	5+6 < 4 → False	[0,4,1,5]	No update
Check	Negative cycle check	All edges	[0,4,1,5]	No dist[u]+w < dist[v]	No change	No negative cycle found

💡 After V-1=3 iterations, no further updates; no negative cycle detected; shortest paths finalized.

State Tracker

Variable	Start	After 1.1	After 1.3	After 1.4	After 1.5	After 2.5	After 3.5	Final
dist	[0,∞,∞,∞]	[0,4,∞,∞]	[0,4,1,∞]	[0,4,1,5]	[0,4,1,5]	[0,4,1,5]	[0,4,1,5]	[0,4,1,5]

Key Insights - 3 Insights

Why do we repeat edge relaxation V-1 times?

Because the longest possible path without cycles has V-1 edges, so repeating ensures all shortest paths are found (see execution_table rows 1.x to 3.x).

What happens if a distance updates after V-1 iterations?

It means a negative weight cycle exists, as shown in the final negative cycle check step where no updates should occur.

Why do we initialize distances with infinity except the start vertex?

To represent unknown distances initially; the start vertex distance is zero because it's the source (see variable_tracker start state).

Visual Quiz - 3 Questions

Look at the execution_table at step 1.3, what is the distance to vertex 2 after relaxation?

A 1

B 5

C ∞

D 4

💡 Hint

Check the 'dist after' column in row 1.3 of execution_table.

At which iteration does the algorithm stop updating distances?

A After first iteration

B After second iteration

C After third iteration

D Never stops

💡 Hint

Look at execution_table rows 2.x and 3.x where no updates happen.

If edge (3->1) had weight -10 instead of 6, what would happen in the negative cycle check?

A No change, no negative cycle

B Negative cycle detected due to further updates

C Algorithm would stop early

D Distances would all become zero

💡 Hint

Consider how a negative weight edge can cause distance updates after V-1 iterations (see key_moments).

Concept Snapshot

Bellman-Ford Algorithm:
- Initialize distances with ∞ except start=0
- Relax all edges V-1 times
- If any edge can still relax, negative cycle exists
- Finds shortest paths even with negative weights
- Time complexity: O(V*E)
- Detects negative weight cycles

Full Transcript

The Bellman-Ford algorithm finds shortest paths from a start vertex to all others in a graph that may have negative edge weights. It starts by setting all distances to infinity except the start vertex, which is zero. Then it repeats relaxing all edges V-1 times, where V is the number of vertices. Relaxing an edge means updating the destination vertex distance if a shorter path is found through the edge. After these iterations, it checks for negative weight cycles by seeing if any edge can still be relaxed. If yes, a negative cycle exists and shortest paths are undefined. Otherwise, the distances represent shortest paths. This process is slower than Dijkstra but works with negative weights and detects negative cycles.

Practice

1. What is the primary purpose of the Bellman-Ford algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the minimum spanning tree of 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 edge 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.

2. Step 2: Recognize its unique feature

   Unlike some algorithms, Bellman-Ford can handle graphs with negative edge weights and detect negative weight cycles.

3. Final Answer:

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

4. Quick Check:

   Bellman-Ford finds shortest paths with negative edges = A [OK]

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

Common Mistakes:

• Confusing Bellman-Ford with algorithms for minimum spanning trees
• Thinking it only works with positive edge weights
• Assuming it sorts vertices or detects cycles in undirected graphs

2. Which of the following is the correct step repeated in the Bellman-Ford algorithm?

easy

A. Relax all edges |V|-1 times

B. Relax all edges once

C. Relax edges only if weights are positive

D. Relax edges in topological order

Solution

1. Step 1: Recall the relaxation process

   Bellman-Ford repeatedly relaxes all edges to update shortest path estimates.

2. Step 2: Identify the number of repetitions

   It performs this relaxation exactly |V|-1 times, where |V| is the number of vertices.

3. Final Answer:

   Relax all edges |V|-1 times -> Option A

4. Quick Check:

   Relax edges |V|-1 times = D [OK]

Hint: Relax edges |V|-1 times to find shortest paths [OK]

Common Mistakes:

• Relaxing edges only once
• Relaxing edges only if weights are positive
• Assuming topological order is required

3. Consider the graph with edges and weights:
A -> B (4), A -> C (5), B -> C (-3), C -> D (2)
Using Bellman-Ford from vertex A, what is the shortest distance to vertex C?

medium

A. 5

B. 1

C. -3

D. 4

Solution

1. Step 1: Initialize distances from A

   Distance to A=0, B=∞, C=∞, D=∞ initially.

2. Step 2: Relax edges repeatedly

   First relaxation: A->B=4, A->C=5. Then B->C updates C to 4 + (-3) = 1. C->D updates D to 1 + 2 = 3.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Shortest path A->B->C = 4 + (-3) = 1 [OK]

Hint: Check paths through neighbors to update shortest distances [OK]

Common Mistakes:

• Ignoring negative edge from B to C
• Taking direct edge A->C without relaxation
• Confusing edge weights with distances

4. You run Bellman-Ford on a graph and after |V|-1 iterations, you find an edge u -> v where distance[u] + weight(u,v) < distance[v]. What does this indicate?

medium

A. The graph contains a negative weight cycle reachable from the source

B. The algorithm has completed successfully with correct distances

C. There is a disconnected vertex in the graph

D. The graph is undirected

Solution

1. Step 1: Understand the relaxation check after iterations

   After |V|-1 relaxations, no edge should improve distances if no negative cycles exist.

2. Step 2: Interpret the condition

   If an edge can still relax a distance, it means a negative weight cycle exists reachable from the source.

3. Final Answer:

   The graph contains a negative weight cycle reachable from the source -> Option A

4. Quick Check:

   Extra relaxation means negative cycle = C [OK]

Hint: Extra relaxation after |V|-1 means negative cycle [OK]

Common Mistakes:

• Thinking algorithm finished correctly despite extra relaxation
• Confusing negative cycle with disconnected vertices
• Assuming graph type (directed/undirected) affects this check

5. Given a graph with vertices V = {S, A, B, C} and edges with weights:
S->A (1), A->B (-1), B->C (-1), C->A (-1)
What will Bellman-Ford detect when run from source S?

hard

A. It will find shortest paths without issues

B. It will report no path to vertex C

C. It will detect a negative weight cycle involving vertices A, B, and C

D. It will fail due to disconnected graph

Solution

1. Step 1: Analyze the cycle formed by A, B, and C

   The edges A->B (-1), B->C (-1), and C->A (-1) form a cycle with total weight -3, which is negative.

2. Step 2: Understand Bellman-Ford behavior on negative cycles

   Bellman-Ford detects negative weight cycles reachable from the source, which prevents shortest path calculation.

3. Final Answer:

   It will detect a negative weight cycle involving vertices A, B, and C -> Option C

4. Quick Check:

   Negative cycle A-B-C with sum -3 detected = B [OK]

Hint: Check cycles' total weight; negative sum means cycle detected [OK]

Common Mistakes:

• Assuming shortest paths exist despite negative cycle
• Ignoring the cycle formed by A, B, and C
• Thinking graph is disconnected when it is not