Bellman Ford Algorithm: Definition, Example, and Use Cases

The Bellman Ford algorithm is a method to find the shortest path from one point to all others in a graph, even if some edges have negative weights. It works by repeatedly relaxing edges and can detect negative weight cycles, unlike some other algorithms.

How It Works

The Bellman Ford algorithm works by gradually improving the shortest path estimates between nodes in a graph. Imagine you want to find the quickest route from your home to all places in a city, but some roads might slow you down or even take you backward (negative weights). The algorithm starts by assuming the distance to the starting point is zero and to all others is infinite.

It then goes through all roads (edges) multiple times, updating the shortest known distance to each place if it finds a quicker route. This process is called "relaxation." By repeating this enough times (one less than the number of places), it ensures the shortest paths are found. If after these steps, a shorter path is still found, it means there is a negative cycle, which the algorithm can detect.

Example

This example shows how Bellman Ford finds shortest paths in a graph with some negative edges but no negative cycles.

python

def bellman_ford(graph, start):
    distance = {node: float('inf') for node in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node]:
                if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight

    # Check for negative weight cycles
    for node in graph:
        for neighbor, weight in graph[node]:
            if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]:
                return "Graph contains a negative weight cycle"

    return distance

# Graph represented as adjacency list
# Each key is a node, values are (neighbor, weight) pairs
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', -3), ('D', 2)],
    'C': [('D', 3)],
    'D': []
}

result = bellman_ford(graph, 'A')
print(result)

Output

{'A': 0, 'B': 4, 'C': 1, 'D': 4}

When to Use

Use the Bellman Ford algorithm when you need to find shortest paths in graphs that may have edges with negative weights. Unlike other algorithms like Dijkstra's, Bellman Ford can handle these negative weights safely and also detect if a negative cycle exists, which means no shortest path is possible.

Real-world examples include routing in networks where some connections might have costs or penalties, financial models with gains and losses, or any system where you want to find the best path but some steps might reduce your total score.

Key Points

• Bellman Ford finds shortest paths from one node to all others in a graph.
• It works with graphs that have negative edge weights.
• It detects negative weight cycles, which means no solution exists.
• It uses repeated edge relaxation over all edges.
• It is slower than some algorithms but more flexible.

Key Takeaways

Bellman Ford finds shortest paths even with negative edge weights.

It detects negative weight cycles to avoid incorrect paths.

It repeatedly relaxes edges to improve distance estimates.

Use it when graphs may have negative weights or cycles.

It is slower but more versatile than Dijkstra's algorithm.