Bellman Ford Algorithm Negative Weights in DSA Rust - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances with infinity

↓

Set source distance to 0

↓

Repeat V-1 times:

↓

For each edge:

↓

Check if distance can be improved

↓

If yes, update distance

↓

Check for negative weight cycles

↓

If found: report cycle

↓

Return shortest distances

The algorithm initializes distances, relaxes edges repeatedly, then checks for negative cycles.

Execution Sample

DSA Rust

let mut dist = vec![f64::INFINITY; 4];
dist[0] = 0.0;
let edges = vec![(0,1,4.0),(0,2,5.0),(1,2,-3.0),(2,3,4.0),(3,1,6.0)];
for _ in 0..3 {
  for &(u, v, w) in &edges {
    if dist[u] + w < dist[v] {
      dist[v] = dist[u] + w;
    }
  }
}

This Rust code runs Bellman-Ford on a graph with 4 nodes (0-3) and edges including negative weights.

Execution Table

Step	Operation	Edge Relaxed	Distance Before	Distance After	Visual State
0	Initialize distances	N/A	[0, ∞, ∞, ∞]	[0, ∞, ∞, ∞]	0 -> ∞ -> ∞ -> ∞
1	Relax edges iteration 1	(0->1,4)	[0, ∞, ∞, ∞]	[0, 4, ∞, ∞]	0 -> 4 -> ∞ -> ∞
2	Relax edges iteration 1	(0->2,5)	[0, 4, ∞, ∞]	[0, 4, 5, ∞]	0 -> 4 -> 5 -> ∞
3	Relax edges iteration 1	(1->2,-3)	[0, 4, 5, ∞]	[0, 4, 1, ∞]	0 -> 4 -> 1 -> ∞
4	Relax edges iteration 1	(2->3,4)	[0, 4, 1, ∞]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
5	Relax edges iteration 1	(3->1,6)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
6	Relax edges iteration 2	(0->1,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
7	Relax edges iteration 2	(0->2,5)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
8	Relax edges iteration 2	(1->2,-3)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
9	Relax edges iteration 2	(2->3,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
10	Relax edges iteration 2	(3->1,6)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
11	Relax edges iteration 3	(0->1,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
12	Relax edges iteration 3	(0->2,5)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
13	Relax edges iteration 3	(1->2,-3)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
14	Relax edges iteration 3	(2->3,4)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
15	Relax edges iteration 3	(3->1,6)	[0, 4, 1, 5]	[0, 4, 1, 5]	0 -> 4 -> 1 -> 5
16	Check negative cycle	All edges	[0, 4, 1, 5]	[0, 4, 1, 5]	No updates, no negative cycle

💡 No distance updates in last iteration, so no negative weight cycle detected.

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 distances update during the first iteration but not in later ones?

During the first iteration (rows 1-5), distances improve because initial values are infinite except source. Later iterations (rows 6-15) find no better paths, so no updates happen.

How does the algorithm detect a negative weight cycle?

After V-1 iterations, the algorithm tries to relax edges again (row 16). If any distance improves, it means a negative cycle exists. Here, no improvements occur, so no cycle.

Why is the number of iterations V-1 (3 here for 4 nodes)?

Because the longest possible path without cycles between any two nodes has at most V-1 edges. Relaxing edges V-1 times ensures shortest paths are found.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the distance to node 2 after relaxing edge (1->2,-3)?

A 5

B ∞

C 1

D 4

💡 Hint

Check the 'Distance After' column at step 3 in execution_table.

At which iteration does the distance array stop changing?

A After iteration 1

B After iteration 2

C After iteration 3

D It keeps changing

💡 Hint

Look at variable_tracker and execution_table rows after iteration 1.

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

A No change, no negative cycle detected

B Distances would update, negative cycle detected

C Algorithm would crash

D Distances would become infinite

💡 Hint

Negative weight edges in cycles cause distance updates after V-1 iterations, see step 16.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances with ∞ except source=0
- Relax all edges V-1 times
- If distances update after V-1 iterations, negative cycle exists
- Handles negative weights safely
- Returns shortest path distances or detects cycles

Full Transcript

Bellman Ford algorithm finds shortest paths from a source node to all others in a graph that may have negative edge weights. It starts by setting all distances to infinity except the source, which is zero. Then it repeats relaxing all edges V-1 times, updating distances if a shorter path is found. After these iterations, it checks once more for any distance improvements. If any distance improves, it means a negative weight cycle exists, and the algorithm reports it. Otherwise, it returns the shortest distances. This example shows a graph with 4 nodes and edges including a negative weight edge. Distances update in the first iteration but stabilize afterward, confirming no negative cycle.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It can handle graphs with negative weight edges.

B. It runs faster on all graphs.

C. It uses less memory.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand the limitation of Dijkstra's algorithm

   Dijkstra's algorithm cannot correctly handle graphs with negative weight edges because it assumes that once a node's shortest path is found, it cannot be improved.

2. Step 2: Identify Bellman-Ford's capability

   Bellman-Ford algorithm can handle negative weight edges and detect negative weight cycles, making it more versatile for such graphs.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option A

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges, Dijkstra doesn't [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Assuming it uses less memory
• Believing it only works on acyclic graphs

2. Which of the following Rust code snippets correctly initializes the distance vector for Bellman-Ford with 5 vertices, starting from vertex 0?

easy

A. let mut dist = vec![i32::MIN; 5]; dist[0] = 0;

B. let mut dist = vec![0; 5]; dist[0] = i32::MAX;

C. let mut dist = vec![0; 5];

D. let mut dist = vec![i32::MAX; 5]; dist[0] = 0;

Solution

1. Step 1: Understand initialization for Bellman-Ford

   Distances to all vertices except the source should be set to a very large number (infinity), here represented by i32::MAX. The source vertex distance is set to 0.

2. Step 2: Check each option

   let mut dist = vec![i32::MAX; 5]; dist[0] = 0; correctly sets all distances to i32::MAX and source (index 0) to 0. Others either invert this or use wrong values.

3. Final Answer:

   let mut dist = vec![i32::MAX; 5]; dist[0] = 0; -> Option D

4. Quick Check:

   Initialize distances with max except source 0 = D [OK]

Hint: Set all distances max except source zero [OK]

Common Mistakes:

• Setting source distance to max instead of zero
• Initializing all distances to zero
• Using i32::MIN which is negative infinity

3. What will be the output distances vector after running one iteration of Bellman-Ford on this graph with edges:
edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4)] starting from vertex 0?
Initial distances: [0, i32::MAX, i32::MAX, i32::MAX]

medium

A. [0, 4, 5, i32::MAX]

B. [0, 4, 1, 5]

C. [0, 4, 5, 9]

D. [0, 4, 1, i32::MAX]

Solution

1. Step 1: Relax edges once from initial distances

   Start distances: [0, MAX, MAX, MAX]. Relax edges:
   - Edge (0->1,4): dist[1] = min(MAX, 0+4) = 4
   - Edge (0->2,5): dist[2] = min(MAX, 0+5) = 5
   - Edge (1->2,-3): dist[2] = min(5, 4-3) = 1
   - Edge (2->3,4): dist[3] = min(MAX, 1+4) = 5

2. Step 2: Determine distances after one iteration

   After relaxing all edges once, distances are [0, 4, 1, 5]. But since the question asks after one iteration (one full pass), all edges are relaxed once, so the final distances are [0, 4, 1, 5].

3. Final Answer:

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

4. Quick Check:

   Relax edges once = [0,4,1,5] [OK]

Hint: Relax all edges once to update distances [OK]

Common Mistakes:

• Not relaxing edges in order
• Ignoring negative edge effect
• Stopping after partial relaxation

4. Consider this Rust code snippet for Bellman-Ford. What is the bug causing incorrect detection of negative cycles?

for _ in 0..graph.len() {
    for &(u, v, w) in &edges {
        if dist[u] != i32::MAX && dist[u] + w < dist[v] {
            dist[v] = dist[u] + w;
        }
    }
}
// Check for negative cycle
for &(u, v, w) in &edges {
    if dist[u] != i32::MAX && dist[u] + w < dist[v] {
        return true; // Negative cycle detected
    }
}
return false;

medium

A. The outer loop should run graph.len() - 1 times, not graph.len() times.

B. The distance vector is not initialized properly.

C. The negative cycle check should be inside the outer loop.

D. Edges should be relaxed in reverse order.

Solution

1. Step 1: Understand Bellman-Ford iteration count

   Bellman-Ford requires relaxing edges exactly |V| - 1 times (where |V| is number of vertices) to find shortest paths. Running it |V| times can cause incorrect behavior.

2. Step 2: Identify the bug in loop count

   The code runs the outer loop graph.len() times (equal to |V|), which is one too many. This can cause false detection of negative cycles.

3. Final Answer:

   The outer loop should run graph.len() - 1 times, not graph.len() times. -> Option A

4. Quick Check:

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

Hint: Relax edges exactly vertices minus one times [OK]

Common Mistakes:

• Running relaxation too many times
• Checking negative cycle inside main loop
• Incorrect distance initialization

5. You have a graph with 4 vertices and edges:
[(0, 1, 1), (1, 2, -1), (2, 3, -1), (3, 1, -1)]. Using Bellman-Ford starting from vertex 0, what will the algorithm detect?

hard

A. No negative cycle, shortest paths found.

B. Algorithm will run infinitely without detection.

C. Negative cycle detected involving vertices 1, 2, and 3.

D. Only positive weight cycles detected.

Solution

1. Step 1: Analyze the cycle formed by edges

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

2. Step 2: Bellman-Ford detects negative cycles reachable from source

   Since this negative cycle is reachable from vertex 0 via edge (0->1), Bellman-Ford will detect it during the negative cycle check.

3. Final Answer:

   Negative cycle detected involving vertices 1, 2, and 3. -> Option C

4. Quick Check:

   Negative cycle in reachable cycle = C [OK]

Hint: Check cycles reachable from source for negative sum [OK]

Common Mistakes:

• Ignoring negative cycle presence
• Assuming algorithm runs infinitely
• Thinking only positive cycles exist