bellman_ford.py

def bellman_ford(n, edges, src):
    dist = [float("inf")] * n
    dist[src] = 0

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

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

    return dist