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.