Skip to content
Hello Python
Algorithm1 Practice1 Interview

Bellman-Ford

Relax every edge repeatedly to support negative weights and detect reachable negative cycles. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Bellman-Ford when the prompt's constraints and required operations match this shape: Relax every edge repeatedly to support negative weights and detect reachable negative cycles.

Pybit demonstrates Bellman-Ford in a professional Python interview workspace.
On this page · Relax Every Edge Repeatedly

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Bellman-Ford Code Labs

Relax Every Edge Repeatedly

Any simple shortest path contains at most V minus one edges. Bellman-Ford performs enough full edge passes for improvements to propagate across paths of increasing edge count.

Stop Early When Nothing Changes

If an entire pass produces no improvement, all reachable shortest distances are already stable and later passes cannot change them.

Trace Bellman-Ford Passes

Reference
def bellman_passes(node_count,edges,start):
    distance=[None]*node_count;distance[start]=0;trace=[]
    for _ in range(node_count-1):
        changed=False;next_distance=distance.copy()
        for source,target,weight in edges:
            if distance[source] is not None:
                candidate=distance[source]+weight
                if next_distance[target] is None or candidate<next_distance[target]:next_distance[target]=candidate;changed=True
        distance=next_distance;trace.append(distance.copy())
        if not changed:break
    return trace
Practice

Implement bellman_passes(node_count,edges,start). Return distances after each full pass, using None for unreachable, and stop when unchanged.

Public tests

  • Propagate paths one edge farther per pass

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Detect Reachable Negative Cycles

After V minus one passes, one more successful relaxation from a reachable source proves a reachable negative cycle. Cycles in unreachable components do not invalidate source distances.

Compute Bellman-Ford Distances

Reference
def bellman_ford(node_count,edges,start):
    distance=[None]*node_count;distance[start]=0
    for _ in range(node_count-1):
        changed=False
        for source,target,weight in edges:
            if distance[source] is not None and (distance[target] is None or distance[source]+weight<distance[target]):distance[target]=distance[source]+weight;changed=True
        if not changed:break
    for source,target,weight in edges:
        if distance[source] is not None and (distance[target] is None or distance[source]+weight<distance[target]):return None
    return distance
Practice

Implement bellman_ford(node_count,edges,start). Return distances or None if a reachable negative cycle exists.

Public tests

  • Detect only reachable negative cycles

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Bellman Ford or Dijkstra

Choose Bellman-Ford for possible negative edges and negative-cycle detection at O(VE). Choose Dijkstra for nonnegative edges and better heap-based performance. DAGs permit one topological relaxation pass.

Explain It in an Interview

Say: “After pass i, paths using at most i edges are represented. V minus one covers every simple path; another improvement requires a reachable negative cycle.” Explain unreachable sentinels and early stopping.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Bellman-Ford complete workflowO(VE)O(VE)Relax every reachable directed edge for at most V-1 passes, then perform one proof pass for a negative cycle.

Space

O(V) for the focused Relax Signed Edges with Bellman-Ford implementation.

Assumptions

  • Every simple shortest path has at most V-1 edges, so repeated relaxation discovers its cost. A further reachable improvement requires a repeated vertex and therefore a reachable negative cycle.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Bellman-Ford invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Distances are upper bounds backed by concrete discovered paths.
  3. A finalized distance cannot later be improved under the stated weight assumptions.
  4. Relax all edges up to V-1 times. Preserve this claim after every transition.
  5. Detect only negative cycles reachable from source. Preserve this claim after every transition.

When To Use Or Avoid Bellman-Ford

Use It When

  • Use Bellman-Ford when this precondition is stated or can be proved: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Use it when this maintained state removes repeated work: Distances are upper bounds backed by concrete discovered paths.

Choose Another Tool When

  • Avoid Bellman-Ford when this precondition is absent: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.

Avoid

def bellman_ford_distances(node_count, edges, source):
    pass

Use instead

def bellman_ford_distances(node_count, edges, source):
    distances = [float('inf')] * node_count
    distances[source] = 0
    for _ in range(node_count - 1):
        changed = False
        for start, end, weight in edges:
            if distances[start] != float('inf') and distances[start] + weight < distances[end]:
                distances[end] = distances[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distances[start] != float('inf') and distances[start] + weight < distances[end]:
            return []
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Relax Signed Edges with Bellman-Ford(opens in a new tab)

Breaking the state transition

Skips negative-cycle detection and returns unstable distances.

Prevent it: Preserve this proof obligation: Every recorded distance is a valid path cost, and the method eventually considers every path that could improve it.

Avoid

def bellman_ford_distances(n,edges,source):
    d=[0]*n
    return d

Use instead

def bellman_ford_distances(node_count, edges, source):
    distances = [float('inf')] * node_count
    distances[source] = 0
    for _ in range(node_count - 1):
        changed = False
        for start, end, weight in edges:
            if distances[start] != float('inf') and distances[start] + weight < distances[end]:
                distances[end] = distances[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distances[start] != float('inf') and distances[start] + weight < distances[end]:
            return []
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Relax Signed Edges with Bellman-Ford(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(VE).

Avoid

def bellman_ford_distances(n,edges,source):
    d=[0]*n
    return d

Use instead

def bellman_ford_distances(node_count, edges, source):
    distances = [float('inf')] * node_count
    distances[source] = 0
    for _ in range(node_count - 1):
        changed = False
        for start, end, weight in edges:
            if distances[start] != float('inf') and distances[start] + weight < distances[end]:
                distances[end] = distances[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distances[start] != float('inf') and distances[start] + weight < distances[end]:
            return []
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.