Bellman Ford

Problem

Given a weighted directed graph, find the shortest path from a source to all other vertices. Unlike Dijkstra, this handles negative edge weights and can detect negative-weight cycles.

Approach

Relax all edges V-1 times. After V-1 iterations, if any edge can still be relaxed, a negative cycle exists.

When to Use

Shortest paths with negative edge weights — currency arbitrage detection, cost networks with rebates/discounts. Detects negative cycles. Prefer Dijkstra when all weights are non-negative.

Complexity

Time	O(V * E)
Space	O(V)

Implementation

SolutionTestsChallenge

bellman_ford

Shortest paths allowing negative edge weights.

Problem

Given a weighted directed graph, find the shortest path from a source to all other vertices. Unlike Dijkstra, this handles negative edge weights and can detect negative-weight cycles.

Approach

Relax all edges V-1 times. After V-1 iterations, if any edge can still be relaxed, a negative cycle exists.

When to use

Shortest paths with negative edge weights — currency arbitrage detection, cost networks with rebates/discounts. Detects negative cycles. Prefer Dijkstra when all weights are non-negative.

Complexity

Time: O(V * E) Space: O(V)

NegativeCycleError

Bases: Exception

Raised when a negative-weight cycle is detected.

Source code in src/algo/graphs/bellman_ford.py

class NegativeCycleError(Exception):
    """Raised when a negative-weight cycle is detected."""

bellman_ford

bellman_ford(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]

Return shortest distances from source to all nodes.

edges is a list of (u, v, weight). Raises :class:NegativeCycleError if a negative cycle is reachable from source.

bellman_ford(4, [(0, 1, 1), (1, 2, 3), (0, 2, 10), (2, 3, 2)], 0) [0, 1, 4, 6]

Source code in src/algo/graphs/bellman_ford.py

def bellman_ford(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]:
    """Return shortest distances from *source* to all nodes.

    *edges* is a list of (u, v, weight).
    Raises :class:`NegativeCycleError` if a negative cycle is
    reachable from *source*.

    >>> bellman_ford(4, [(0, 1, 1), (1, 2, 3), (0, 2, 10), (2, 3, 2)], 0)
    [0, 1, 4, 6]
    """
    dist: list[float] = [INF] * num_nodes
    dist[source] = 0

    for _ in range(num_nodes - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] < INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] < INF and dist[u] + w < dist[v]:
            raise NegativeCycleError(
                "Graph contains a negative-weight cycle reachable from source"
            )

    return dist

tests/graphs/test_bellman_ford.py

"""Tests for Bellman-Ford shortest path algorithm."""

import pytest

from algo.graphs.bellman_ford import INF, NegativeCycleError, bellman_ford


class TestBellmanFord:
    def test_simple_graph(self) -> None:
        edges = [(0, 1, 1), (1, 2, 3), (0, 2, 10), (2, 3, 2)]
        assert bellman_ford(4, edges, 0) == [0, 1, 4, 6]

    def test_negative_weight(self) -> None:
        edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3)]
        assert bellman_ford(3, edges, 0) == [0, 4, 1]

    def test_negative_cycle_raises(self) -> None:
        edges = [(0, 1, 1), (1, 2, -1), (2, 0, -1)]
        with pytest.raises(NegativeCycleError):
            bellman_ford(3, edges, 0)

    def test_unreachable_node(self) -> None:
        edges = [(0, 1, 5)]
        dist = bellman_ford(3, edges, 0)
        assert dist == [0, 5, INF]

    def test_single_node(self) -> None:
        assert bellman_ford(1, [], 0) == [0]

    def test_all_zero_weights(self) -> None:
        edges = [(0, 1, 0), (1, 2, 0)]
        assert bellman_ford(3, edges, 0) == [0, 0, 0]

Implement it yourself

Run: just challenge graphs bellman_ford

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

bellman_ford

Shortest paths allowing negative edge weights.

Problem

Given a weighted directed graph, find the shortest path from a source to all other vertices. Unlike Dijkstra, this handles negative edge weights and can detect negative-weight cycles.

Approach

Relax all edges V-1 times. After V-1 iterations, if any edge can still be relaxed, a negative cycle exists.

When to use

Shortest paths with negative edge weights — currency arbitrage detection, cost networks with rebates/discounts. Detects negative cycles. Prefer Dijkstra when all weights are non-negative.

Complexity

Time: O(V * E) Space: O(V)

NegativeCycleError

Bases: Exception

Raised when a negative-weight cycle is detected.

Source code in src/algo/graphs/bellman_ford.py

class NegativeCycleError(Exception):
    """Raised when a negative-weight cycle is detected."""

bellman_ford

bellman_ford(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]

Return shortest distances from source to all nodes.

edges is a list of (u, v, weight). Raises :class:NegativeCycleError if a negative cycle is reachable from source.

bellman_ford(4, [(0, 1, 1), (1, 2, 3), (0, 2, 10), (2, 3, 2)], 0) [0, 1, 4, 6]

Source code in src/algo/graphs/bellman_ford.py

def bellman_ford(
    num_nodes: int,
    edges: Sequence[tuple[int, int, float]],
    source: int,
) -> list[float]:
    """Return shortest distances from *source* to all nodes.

    *edges* is a list of (u, v, weight).
    Raises :class:`NegativeCycleError` if a negative cycle is
    reachable from *source*.

    >>> bellman_ford(4, [(0, 1, 1), (1, 2, 3), (0, 2, 10), (2, 3, 2)], 0)
    [0, 1, 4, 6]
    """
    dist: list[float] = [INF] * num_nodes
    dist[source] = 0

    for _ in range(num_nodes - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] < INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] < INF and dist[u] + w < dist[v]:
            raise NegativeCycleError(
                "Graph contains a negative-weight cycle reachable from source"
            )

    return dist