Shortest Path: BFS, Dijkstra, and When Each Works

Find the shortest path" splits on whether edges have weights. Unweighted: BFS gives shortest-by-hops. Weighted: Dijkstra gives shortest-by-cost — and Dijkstra is just BFS where the frontier is ordered by cost instead of arrival.

Dijkstra in one function

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                    # stale entry — already found shorter
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

The priority queue pops the cheapest frontier node — that's what makes it Dijkstra instead of BFS. Each edge relaxation updates dist if a cheaper path was found.

The constraints

• Non-negative weights only — Dijkstra assumes "once we pop a node, we've found its shortest path." Negative weights break that assumption (Bellman-Ford handles them, at O(VE) cost).
• Dense graphs vs sparse — Dijkstra with a heap is O((V+E) log V); without one it's O(V²). For road networks (sparse), the heap version is right.

::exercise(dijkstra-limit)

Field notes

• A* is Dijkstra + a heuristic — a lower-bound estimate of the remaining distance — that guides the search toward the goal. Games, maps, and routing all use it.
• "Shortest path" isn't always the goal — sometimes it's "most reliable" or "lowest latency" — the weight function is the design choice.
• Floyd-Warshall gives all-pairs shortest path in O(V³) — fine for small graphs, wrong for large ones.