Bellman-Ford Algorithm — Working, Example and Applications

The Bellman-Ford algorithm computes the shortest path from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford can correctly handle graphs with negative edge weights, and it can also detect negative weight cycles.

How It Works

• Initialize the distance to the source as 0 and all other vertices as infinity.
• Relax every edge — if going through an edge gives a shorter path to a vertex, update its distance.
• Repeat the relaxation process for (V - 1) iterations, where V is the number of vertices.
• Perform one more pass; if any distance can still be improved, a negative weight cycle exists.

def bellman_ford(edges, num_vertices, source):
    distance = [float('inf')] * num_vertices
    distance[source] = 0

    for _ in range(num_vertices - 1):
        for u, v, weight in edges:
            if distance[u] != float('inf') and distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight

    for u, v, weight in edges:
        if distance[u] != float('inf') and distance[u] + weight < distance[v]:
            raise ValueError("Graph contains a negative weight cycle")

    return distance

Worked Example

Consider a graph with edges (A→B, 4), (A→C, 5), (B→C, -3), (C→D, 2). Starting from A, Bellman-Ford relaxes each edge repeatedly: distance to B becomes 4, distance to C is improved to 1 via B (4 + -3), and distance to D becomes 3 (1 + 2). This shows how the algorithm correctly handles the negative edge B→C.

Complexity

Applications

• Routing protocols such as RIP (Routing Information Protocol).
• Detecting arbitrage opportunities in currency exchange graphs.
• Network flow problems where edge costs can be negative.