Bellman-Ford Algorithm

Analogy categoryAnalogies

Introduction

Bellman-Ford computes the shortest distance from a single source vertex to every other vertex in a weighted directed graph. Its defining advantage over Dijkstra's algorithm is that it correctly handles negative edge weights -- Dijkstra's greedy strategy of always finalizing the nearest unvisited vertex breaks down when a later negative edge could still shorten an already-finalized distance. Bellman-Ford instead relies on repeated relaxation of every edge, which naturally accounts for negative weights, and as a byproduct it can detect whether the graph contains a negative-weight cycle reachable from the source, in which case no shortest path is well-defined.

🏏

Cricket analogy: Dijkstra's approach is like a captain locking in the 'best' batting order after each over and never revisiting it, but if a late over reveals a negative swing (a batter's form collapsing), only Bellman-Ford's repeated re-checking of every pairing catches it.

Algorithm/Syntax

python

def bellman_ford(n, edges, source):
    """n: number of vertices. edges: list of (u, v, weight).
    Returns (dist, has_negative_cycle).
    """
    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0

    # Relax all edges V - 1 times
    for _ in range(n - 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  # early exit: no changes means distances have converged

    # One more pass: if anything still relaxes, a negative cycle exists
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break

    return dist, has_negative_cycle

Explanation

The algorithm relies on a simple fact: any shortest path in a graph with no negative cycle visits at most V-1 edges (since a shortest path never repeats a vertex). Relaxing every edge once guarantees that all shortest paths using at most 1 edge are correct; after k full passes, all shortest paths using at most k edges are correct. So after V-1 passes over all E edges, every shortest path (which uses at most V-1 edges) has been correctly computed. The extra V-th pass checks for further improvement: if any edge can still be relaxed, that means some path is using more than V-1 edges to reduce its distance, which is only possible if a negative-weight cycle exists somewhere along the way, since normal shortest paths never need to revisit a vertex.

🏏

Cricket analogy: Since a batter can only face at most V-1 bowling changes before the innings shortest path to a target score is set, one full pass through all bowling matchups locks in every 1-change path, and V-1 passes lock in every possible path, mirroring Bellman-Ford's V-1 relaxation rounds.

Example

python

# Graph with a negative edge but no negative cycle
edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4), (3, 1, -6), (1, 4, 5)]
dist, neg_cycle = bellman_ford(5, edges, source=0)
print(dist)        # [0, 4, 5, 9, 9]
print(neg_cycle)   # False

# Graph with a genuine negative cycle: 1 -> 2 -> 3 -> 1 has total weight -3 + 4 - 2 = -1
cycle_edges = [(0, 1, 1), (1, 2, -3), (2, 3, 4), (3, 1, -2)]
dist2, neg_cycle2 = bellman_ford(4, cycle_edges, source=0)
print(neg_cycle2)  # True -- distances into the cycle keep shrinking forever

Complexity

Time complexity is O(V * E), since the algorithm performs up to V-1 relaxation passes, each touching every edge once (plus one extra pass for cycle detection). This is worse than Dijkstra's O(E log V) with a binary heap on graphs without negative weights, which is why Dijkstra is preferred whenever all edge weights are non-negative. Space complexity is O(V) for the distance array. Note that Bellman-Ford, unlike Dijkstra, requires no special data structure (no priority queue), only a plain list of edges.

🏏

Cricket analogy: Running V-1 full passes over every possible bowling-batting matchup, each touching every matchup once, costs O(V*E), noticeably slower than a Dijkstra-style greedy pick when no matchup ever 'gains' runs, which is why the greedy pick is preferred on non-negative pitches.

Key Takeaways

Bellman-Ford finds single-source shortest paths in O(V * E) time by relaxing every edge V-1 times.
It correctly handles negative edge weights, which Dijkstra's greedy approach cannot.
A V-th relaxation pass that still finds an improvement reveals a negative-weight cycle reachable from the source.
It is slower than Dijkstra on graphs with only non-negative weights, so Dijkstra should be preferred there.
Applications include currency arbitrage detection and routing protocols like RIP, where negative cycles matter.

Practice what you learned

1. Why can Dijkstra's algorithm produce incorrect results on graphs with negative edge weights?

2. How many times does Bellman-Ford relax all edges before checking for a negative cycle?

3. What does it mean if, on the V-th pass, an edge relaxation still reduces a vertex's distance?

4. What is the time complexity of Bellman-Ford on a graph with V vertices and E edges?

Was this page helpful?

Floyd-Warshall Algorithm

Network Flow Basics

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#BellmanFordAlgorithm#Bellman#Ford#Algorithm#Syntax#StudyNotes#SkillVeris