Bellman Ford Algorithm Negative Weights in DSA Typescript - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances with Infinity except source=0

↓

Relax all edges

↓

Repeat relaxation V-1 times

↓

Check for negative weight cycles

↓

Report negative cycle

Start by setting distances, then relax edges repeatedly to find shortest paths, finally check for negative cycles.

Execution Sample

DSA Typescript

const edges = [
  {from: 0, to: 1, weight: 4},
  {from: 0, to: 2, weight: 5},
  {from: 1, to: 2, weight: -3}
];
const dist = bellmanFord(edges, 3, 0);

This code runs Bellman Ford on a graph with 3 nodes and edges including a negative weight edge.

Execution Table

Step	Operation	Edge Relaxed	Distance Array Before	Distance Array After	Visual State
0	Initialize distances	N/A	[∞, ∞, ∞]	[0, ∞, ∞]	0:0, 1:∞, 2:∞
1	Relax edge	0->1 (4)	[0, ∞, ∞]	[0, 4, ∞]	0:0, 1:4, 2:∞
2	Relax edge	0->2 (5)	[0, 4, ∞]	[0, 4, 5]	0:0, 1:4, 2:5
3	Relax edge	1->2 (-3)	[0, 4, 5]	[0, 4, 1]	0:0, 1:4, 2:1
4	Relax edge	0->1 (4)	[0, 4, 1]	[0, 4, 1]	No change
5	Relax edge	0->2 (5)	[0, 4, 1]	[0, 4, 1]	No change
6	Relax edge	1->2 (-3)	[0, 4, 1]	[0, 4, 1]	No change
7	Check negative cycle	N/A	[0, 4, 1]	[0, 4, 1]	No negative cycle found
8	End	N/A	N/A	N/A	Distances finalized

💡 After V-1=2 relaxations, no distance updates; no negative cycle detected; algorithm ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	Final
dist	[∞, ∞, ∞]	[0, 4, ∞]	[0, 4, 5]	[0, 4, 1]	[0, 4, 1]	[0, 4, 1]
step	0	1	2	3	6	8

Key Moments - 3 Insights

Why do we relax all edges V-1 times?

Because the longest possible path without cycles has V-1 edges, relaxing that many times ensures shortest paths are found, as shown in steps 1 to 6 where distances update until stable.

What happens if a distance does not change during relaxation?

If no distance updates occur during a full pass (like steps 4-6), it means shortest paths are found and further relaxations won't change distances.

How does the algorithm detect negative weight cycles?

After V-1 relaxations, if any edge can still relax a distance (not shown here), it means a negative cycle exists, as checked in step 7.

Visual Quiz - 3 Questions

Look at the execution table, what is the distance to node 2 after step 3?

A ∞

B 5

C 1

D 4

💡 Hint

Check the 'Distance Array After' column at step 3 in the execution table.

At which step does the algorithm confirm no negative weight cycle exists?

A Step 7

B Step 3

C Step 6

D Step 1

💡 Hint

Look for the 'Check negative cycle' operation in the execution table.

If the edge 1->2 had weight -5 instead of -3, what would happen at step 3?

A Distance to node 2 becomes 4

B Distance to node 2 becomes -1

C Distance to node 2 remains 5

D Distance to node 2 becomes 0

💡 Hint

Calculate new distance: dist[1] + weight = 4 + (-5) = -1, check step 3 logic.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances: source=0, others=∞
- Relax all edges V-1 times
- Update distances if shorter path found
- Check for negative cycles by extra relaxation
- Detects shortest paths even with negative weights
- Stops if no changes or negative cycle found

Full Transcript

Bellman Ford algorithm starts by setting all distances to infinity except the source node which is zero. It then relaxes all edges repeatedly for V-1 times, where V is the number of vertices. Relaxing means checking if going through an edge improves the known shortest distance to a node. After these relaxations, the algorithm checks for negative weight cycles by trying to relax edges once more. If any distance improves, a negative cycle exists. Otherwise, the shortest distances are finalized. This example shows distances updating step-by-step and no negative cycle detected.