Shortest Path Algorithms (Bellman-Ford)

The Bellman-Ford algorithm is a shortest path algorithm that computes the shortest distances from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford supports negative edge weights and can also detect negative-weight cycles.

Because of this, Bellman-Ford is especially useful in systems where costs may decrease over time or where validating graph correctness is required.

When to Use Bellman-Ford

Bellman-Ford is appropriate when:

• The graph is weighted
• Edge weights may be negative
• You need to detect negative cycles
• Graph size is moderate (performance is slower than Dijkstra)

Key Idea

The algorithm is based on edge relaxation.

Relaxing an edge u → v with weight w means:

if distance[u] + w < distance[v]:
    distance[v] = distance[u] + w

By repeatedly relaxing all edges, shortest paths are gradually discovered.

Why It Works

In a graph with V vertices:

• The longest possible simple path has at most V - 1 edges
• Repeating edge relaxation V - 1 times guarantees shortest paths
• A further pass that still improves distances indicates a negative cycle

Algorithm Steps

1. Initialize all distances to infinity

2. Set the source distance to 0

3. Repeat V - 1 times:

   • Relax every edge

4. Perform one extra pass:

   • If any distance improves → negative cycle exists

Example Graph

A --4--> B
|        |
5       -2
|        |
v        v
C --3--> D

Bellman-Ford can correctly handle the -2 edge, while Dijkstra cannot.

Graph Representation

This implementation uses an edge list, which makes Bellman-Ford easy to express.

Rust Implementation

use std::collections::HashMap;

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

pub fn bellman_ford(
    vertices: &[i32],
    edges: &[Edge],
    source: i32,
) -> Result<HashMap<i32, i32>, &'static str> {
    let mut distance = HashMap::new();

    for &v in vertices {
        distance.insert(v, i32::MAX);
    }
    distance.insert(source, 0);

    // Relax edges V - 1 times
    for _ in 0..vertices.len() - 1 {
        let mut updated = false;

        for edge in edges {
            let u = edge.from;
            let v = edge.to;

            if distance[&u] != i32::MAX {
                let new_dist = distance[&u] + edge.weight;
                if new_dist < distance[&v] {
                    distance.insert(v, new_dist);
                    updated = true;
                }
            }
        }

        if !updated {
            break;
        }
    }

    // Check for negative-weight cycles
    for edge in edges {
        let u = edge.from;
        let v = edge.to;

        if distance[&u] != i32::MAX && distance[&u] + edge.weight < distance[&v] {
            return Err("Graph contains a negative-weight cycle");
        }
    }

    Ok(distance)
}

Example Usage

fn main() {
    let vertices = vec![1, 2, 3, 4];

    let edges = vec![
        Edge { from: 1, to: 2, weight: 4 },
        Edge { from: 1, to: 3, weight: 5 },
        Edge { from: 2, to: 4, weight: -2 },
        Edge { from: 3, to: 4, weight: 3 },
    ];

    match bellman_ford(&vertices, &edges, 1) {
        Ok(distances) => {
            for (v, d) in distances {
                println!("Distance from 1 to {} = {}", v, d);
            }
        }
        Err(err) => println!("{}", err),
    }
}

Output:

Distance from 1 to 1 = 0
Distance from 1 to 2 = 4
Distance from 1 to 3 = 5
Distance from 1 to 4 = 2

Time and Space Complexity

Time Complexity

This is slower than Dijkstra, especially for large graphs.

Space Complexity

Bellman-Ford vs Dijkstra

Limitations

• Slower than Dijkstra
• Not suitable for very large graphs
• Single-source only

Summary

• Bellman-Ford handles negative edge weights
• Detects negative-weight cycles
• Uses repeated edge relaxation
• Guarantees correctness at higher computational cost

Playground Links

Rust - Bellman-Ford Algorithm