Shortest-path modeling

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

Define a path's cost as the sum of its edge weights. Clarify direction, unreachable nodes, and whether constraints such as stops or remaining fuel belong in the state. One distance per vertex is insufficient when future choices depend on additional state.

Work through an example

Cheapest route with at most k stops needs (vertex,edges_used), because reaching a vertex cheaply after exhausting the budget can be worse than a pricier early arrival.

Time and space complexity

Model size determines complexity; expanded states multiply vertices and edges.

Why it works

Distances represent the cheapest known cost for the complete chosen state.

Common mistakes

Minimizing edge count is different from minimizing weight.
Ignoring resource state can discard useful paths.

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.