Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python Bellman-Ford: negative edges and reachable negative cycles

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

Bellman-Ford relaxes weighted directed edges repeatedly and can detect a negative-cost cycle reachable from a selected source.

Download Python source kit

Operation contract

The route function accepts bounded integer node IDs and signed integer costs. An unreachable node remains None. At most V minus one relaxation rounds establish finite shortest-path costs when no reachable negative cycle exists; one more improving edge proves that a finite answer cannot be supplied for the reachable cycle. A disconnected negative cycle does not invalidate this source’s reachable routes.

Failure and ownership boundary

Dijkstra requires a different cost contract. Negative edges are accepted here, while malformed endpoints and boolean costs are rejected before relaxation. The caller receives a fresh cost list; the edge sequence is unchanged. This implementation reports a cycle error without returning a cycle witness or marking every affected destination. Python Dijkstra: nonnegative weights and stale heap entries and Python graph BFS: mark a vertex when it enters the queue use cheaper algorithms under narrower assumptions.

Working program

python
def signed_routes(count, edges, source):
    if type(count) is not int or not 1 <= count <= 32:
        raise ValueError("node budget exceeded")
    if type(source) is not int or not 0 <= source < count or len(edges) > 512:
        raise ValueError("invalid source or edge budget")
    for start, end, weight in edges:
        if any(type(value) is not int for value in (start, end, weight)):
            raise ValueError("integer edges required")
        if not 0 <= start < count or not 0 <= end < count or abs(weight) > 1000000:
            raise ValueError("invalid edge")
    costs = [None] * count
    costs[source] = 0
    for _ in range(count - 1):
        changed = False
        for start, end, weight in edges:
            if costs[start] is not None:
                candidate = costs[start] + weight
                if costs[end] is None or candidate < costs[end]:
                    costs[end] = candidate
                    changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if costs[start] is not None and (costs[end] is None or costs[start] + weight < costs[end]):
            raise ValueError("reachable negative cycle")
    return costs

print(signed_routes(4, [(0, 1, 5), (1, 2, -2), (0, 2, 8)], 0))
try:
    signed_routes(3, [(0, 1, 1), (1, 2, -2), (2, 1, 1)], 0)
except ValueError:
    print("reachable negative cycle rejected")

Output

Output
[0, 5, 3, None]
reachable negative cycle rejected

Costs and limits

Worst-case relaxation time is O(VE), with O(V) cost storage beyond the supplied edges. Early stopping helps settled inputs but does not improve the worst-case bound. Integer digit costs grow with represented values.

Common Mistakes

  • Rejecting every negative edge would change this algorithm’s contract.
  • An unreachable negative cycle does not affect source-specific finite costs.

Connected lessons

Python Dijkstra: nonnegative weights and stale heap entries, Python graph BFS: mark a vertex when it enters the queue, Python topological sort: dependency order and cycle rejection.

Trace the related workflow

Python Floyd-Warshall: all-pairs costs with negative-cycle rejection.

python
bellman-ford
Storage details