Bellman Ford Algorithm Negative Weights in DSA Rust

Mental Model

Bellman Ford finds shortest paths from one point to all others even if some paths have negative costs, by relaxing edges repeatedly.

Analogy: Imagine you want to find the cheapest way to travel between cities, but some roads give you discounts (negative costs). You check all roads multiple times to update your best prices until no cheaper way is found.

Graph with nodes and edges:

  (A)
  / \
-1   4
 /     \
(B)---(C)
  \    /
   2  -3
    \ /
    (D)

Edges have weights including negatives (-1, -3).

Dry Run Walkthrough

Input: Graph with edges: A->B(-1), A->C(4), B->C(3), B->D(2), D->B(1), D->C(-3); start=A

Goal: Find shortest distances from A to all nodes, handling negative weights correctly

Step 1: Initialize distances: A=0, others=∞

Distances: A=0, B=∞, C=∞, D=∞

Why: Start with zero distance to source and unknown (infinite) to others

Step 2: Relax all edges first time

Distances: A=0, B=-1 (via A->B), C=4 (via A->C), D=∞

Why: Update distances using direct edges from A

Step 3: Relax all edges second time

Distances: A=0, B=-1, C=2 (via B->C), D=1 (via B->D)

Why: Use updated B distance to improve C and D

Step 4: Relax all edges third time

Distances: A=0, B=-1, C=-2 (via D->C), D=1

Why: Use D->C edge with negative weight to reduce C distance

Step 5: Check for negative cycles by relaxing edges again

No distance changes

Why: No further improvements means no negative cycles

Result:

Distances: A=0, B=-1, C=-2, D=1

Annotated Code

DSA Rust

use std::collections::HashMap;

#[derive(Debug)]
struct Edge {
    from: char,
    to: char,
    weight: i32,
}

fn bellman_ford(edges: &[Edge], start: char) -> Result<HashMap<char, i32>, String> {
    let mut dist = HashMap::new();
    // Initialize distances
    for edge in edges {
        dist.insert(edge.from, i32::MAX);
        dist.insert(edge.to, i32::MAX);
    }
    dist.insert(start, 0);

    let vertices: Vec<char> = dist.keys().cloned().collect();
    let v_count = vertices.len();

    // Relax edges v_count - 1 times
    for _ in 0..v_count - 1 {
        let mut updated = false;
        for edge in edges {
            let from_dist = *dist.get(&edge.from).unwrap_or(&i32::MAX);
            if from_dist != i32::MAX {
                let to_dist = *dist.get(&edge.to).unwrap_or(&i32::MAX);
                if from_dist.checked_add(edge.weight).map_or(false, |new_dist| new_dist < to_dist) {
                    dist.insert(edge.to, from_dist + edge.weight);
                    updated = true;
                }
            }
        }
        if !updated {
            break; // No update means shortest paths found
        }
    }

    // Check for negative weight cycles
    for edge in edges {
        let from_dist = *dist.get(&edge.from).unwrap_or(&i32::MAX);
        let to_dist = *dist.get(&edge.to).unwrap_or(&i32::MAX);
        if from_dist != i32::MAX && from_dist.checked_add(edge.weight).map_or(false, |new_dist| new_dist < to_dist) {
            return Err("Graph contains a negative weight cycle".to_string());
        }
    }

    Ok(dist)
}

fn main() {
    let edges = vec![
        Edge { from: 'A', to: 'B', weight: -1 },
        Edge { from: 'A', to: 'C', weight: 4 },
        Edge { from: 'B', to: 'C', weight: 3 },
        Edge { from: 'B', to: 'D', weight: 2 },
        Edge { from: 'D', to: 'B', weight: 1 },
        Edge { from: 'D', to: 'C', weight: -3 },
    ];

    match bellman_ford(&edges, 'A') {
        Ok(distances) => {
            let mut keys: Vec<_> = distances.keys().cloned().collect();
            keys.sort();
            for k in keys {
                println!("Distance from A to {} is {}", k, distances[&k]);
            }
        }
        Err(e) => println!("Error: {}", e),
    }
}

dist.insert(start, 0);

Set distance to start node as zero

for _ in 0..v_count - 1 {

Repeat relaxation for all vertices minus one times

if from_dist + edge.weight < to_dist {

Relax edge if shorter path found

if !updated { break; }

Stop early if no distance updates

if from_dist != i32::MAX && from_dist + edge.weight < to_dist { return Err(...); }

Detect negative weight cycle if further relaxation possible

Output

Distance from A to A is 0

Distance from A to B is -1

Distance from A to C is -2

Distance from A to D is 1

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times where V is vertices and E is edges

Space: O(V) to store distances for each vertex

vs Alternative: Unlike Dijkstra which fails with negative weights, Bellman Ford handles them but is slower due to repeated edge checks

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and returns error

DSA Rust

if from_dist != i32::MAX && from_dist + edge.weight < to_dist { return Err(...) }

Graph with unreachable nodes

Distances remain at infinity (i32::MAX) for unreachable nodes

DSA Rust

dist.insert(edge.from, i32::MAX); dist.insert(edge.to, i32::MAX);

Graph with single node

Distance to start node is zero, no edges to relax

DSA Rust

dist.insert(start, 0);

When to Use This Pattern

When you see shortest path problems with possible negative edge weights, reach for Bellman Ford because it handles negatives and detects cycles.

Common Mistakes

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final pass to detect if any edge can still be relaxed, indicating a negative cycle

Mistake: Initializing distances incorrectly, missing some vertices
Fix: Initialize distances for all vertices found in edges before relaxation

Summary

Finds shortest paths from one node to all others even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Repeatedly relax edges to update shortest paths until no improvements or a negative cycle is found.

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