Bellman-Ford and negative edges

What is a weighted graph?

A weighted graph attaches a number to each edge, such as a distance, cost, or travel time. A path is a sequence of connected edges; its total cost is the sum of their weights. A shortest-path algorithm finds the least total cost under the problem’s rules. Different rules, especially negative weights, require different algorithms.

Example: A → B costs 4 and B → C costs 3, so that route costs 7. If A → C costs 10, the route through B is cheaper even though it uses more edges.

Helpful before this chapter

If these ideas are new, begin with:

Heaps and priority queues Graph representations and traversal Graph ordering and connectivity

Understand the idea

Bellman-Ford relaxes every edge over repeated passes. After enough passes, shortest simple paths with at most V-1 edges are represented. A further improvement indicates a reachable negative cycle.

Work through an example

Edges 0→1=4,0→2=1,2→1=-2 produce distance -1 to 1. A reachable cycle with total -2 allows cost to decrease indefinitely.

Time and space complexity

O(VE) time/O(V) distance state; early stopping is allowed after no changes.

Why it works

After pass t, all shortest paths using at most t edges are found or improved; in-place updates may find longer paths earlier.

Common mistakes

Unreachable negative cycles do not affect source distances.
Guard infinity before arithmetic.

Chapter lab · Python implementation

Weighted objectives require precise distinctions. Dijkstra finds cheapest routes from one source with nonnegative weights. Bellman-Ford permits negative edges and detects reachable negative cycles. A minimum spanning tree minimizes the total edges needed to connect all vertices; it does not minimize every source-to-vertex route.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

import heapq

def dijkstra(graph,start):
    if any(w<0 for edges in graph.values() for _,w in edges):
        raise ValueError('nonnegative weights required')
    distances={start:0}; heap=[(0,start)]
    while heap:
        cost,node=heapq.heappop(heap)
        if cost!=distances[node]: continue
        for neighbor,weight in graph.get(node,[]):
            candidate=cost+weight
            if candidate<distances.get(neighbor,float('inf')):
                distances[neighbor]=candidate
                heapq.heappush(heap,(candidate,neighbor))
    return distances

def bellman_ford(n,edges,start):
    d=[float('inf')]*n; d[start]=0
    for _ in range(n-1):
        changed=False
        for a,b,w in edges:
            if d[a]!=float('inf') and d[a]+w<d[b]:
                d[b]=d[a]+w; changed=True
        if not changed: break
    if any(d[a]!=float('inf') and d[a]+w<d[b] for a,b,w in edges):
        raise ValueError('reachable negative cycle')
    return d

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':[('B',4),('C',1)],'C':[('B',2)],'B':[]}
assert dijkstra(g,'A')=={'A':0,'B':3,'C':1}
assert bellman_ford(3,[(0,1,4),(0,2,1),(2,1,-2)],0)==[0,-1,1]
try: bellman_ford(2,[(0,1,-1),(1,0,-1)],0)
except ValueError: pass
else: raise AssertionError('negative cycle not detected')

CHECK YOUR UNDERSTANDING

What is a weighted graph?

Initialize source A.