Shortest Paths

What you'll learn

Add weights to edges and "shortest" means cheapest, not fewest. This module covers the great shortest-path algorithms — Dijkstra for non-negative weights, Bellman-Ford when edges can be negative, Floyd-Warshall for all pairs, and A* for guided search.

By the end you'll be able to:

• Explain edge relaxation, the shared core
• Run Dijkstra with a priority queue
• Handle negative edges with Bellman-Ford
• Choose the right algorithm for the graph

Edge relaxation

Every shortest-path algorithm is built on one operation: relaxation. If the known distance to u plus the edge u→v beats the known distance to v, we've found a better route — update it: if dist[u] + w < dist[v]: dist[v] = dist[u] + w. The algorithms differ only in the order they relax edges.

Dijkstra's algorithm

Dijkstra is greedy: repeatedly finalize the closest not-yet-finalized vertex (via a min-priority-queue), then relax its edges. It requires non-negative weights. Watch distances (the badges) fall as edges relax:

Dijkstra in code

import heapq

def dijkstra(adj, start):            # adj[u] = [(v, w), ...]
    dist = {u: float("inf") for u in adj}
    dist[start] = 0
    pq = [(0, start)]                # min-heap of (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                 # stale entry
        for v, w in adj[u]:
            if d + w < dist[v]:      # relax the edge
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Bellman-Ford

When edges can be negative, Bellman-Ford relaxes every edge, V − 1 times. After that, all shortest paths are final; if any edge still improves, a negative cycle exists. It trades speed (O(V·E)) for the ability to handle — and detect — negatives:

def bellman_ford(edges, n, start):   # edges = [(u, v, w)]
    dist = [float("inf")] * n
    dist[start] = 0
    for _ in range(n - 1):           # relax ALL edges n-1 times
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:            # one more pass:
        if dist[u] + w < dist[v]:
            return None              # a still-improving edge => negative cycle
    return dist

Floyd-Warshall & A*

• Floyd-Warshall finds shortest paths between all pairs in O(V³). It's a tiny DP: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), trying each intermediate k. Perfect for small, dense graphs.
• A* speeds up single-target search by adding a heuristic — an estimate of the distance remaining to the goal (e.g. straight-line distance on a map). It expands vertices by dist + heuristic, so it heads toward the target instead of spreading everywhere. With an admissible (never-overestimating) heuristic, it's optimal.

Recap & quick check

Next: not the shortest path, but the cheapest way to connect everything. Next up: Module 27 — Minimum Spanning Trees.