Bellman-Ford

Bellman-Ford Algorithm

Bellman-Ford finds shortest paths from a source like Dijkstra, but handles negative edge weights. It also detects negative-weight cycles (where the shortest path would be −∞).

Algorithm

Relax all edges n-1 times (the maximum number of edges in any shortest path without cycles):

def bellman_ford(n, edges, src):
    # edges = [(u, v, weight)]
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None   # negative cycle detected

    return dist

Why n-1 Iterations?

A shortest path in a graph without negative cycles visits at most n-1 edges. After n-1 relaxations, all shortest paths are found. A n-th relaxation that still improves means there's a negative cycle.

Dijkstra vs Bellman-Ford

Your Task

Implement bellman_ford(n, edges, src) that returns a list of shortest distances from src to every node (index = node id), or None if a negative cycle is detected.