Shortest Paths: Dijkstra, Bellman-Ford, A*

1Fewest hops is not cheapest

BFS answers 'fewest edges'. Almost no real question is about edges — it is about minutes, dollars, or kilometres.

Formally: in a weighted graph every edge (u, v) has a weight w(u, v). The cost of a path is the sum of its edge weights, and a shortest path from s to t is any path of minimum total cost. There may be several; they all count.

BFS solves the special case where every weight is 1. That is not a limitation to be embarrassed about — it is the reason BFS is so fast. It can expand in rings because in an unweighted graph the ring is the distance.

Three facts hold for every algorithm in this chapter, and each one is used later:

• Optimal substructure. If the shortest path from s to t passes through v, then the part from s to v is itself a shortest s–v path. If it were not, you could swap in a cheaper one and beat the path you called shortest.
• A shortest path never repeats a vertex, provided there are no negative cycles. Going round a loop of non-negative weight cannot help, so it can always be cut out.
• Shortest paths form a tree. Every vertex needs to remember only one predecessor, not a whole path. That is why every implementation below stores a prev dictionary and reconstructs at the end.

2Relaxation: the only idea in this chapter

Every algorithm here is the same three lines, run in a different order. Learn the three lines and the rest is scheduling.

Keep a table dist of the best cost found so far to each vertex, starting at infinity everywhere except the source. Then repeatedly ask one question about one edge:

def relax(dist, prev, u, v, w):
    """Can going u -> v improve our current best route to v?"""
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w   # yes: record the cheaper cost
        prev[v] = u             # and remember how we got here
        return True
    return False                # no: the route we already had is at least as good

Two invariants make relaxation safe, and they are worth stating because every proof in the chapter leans on them:

• dist[v] is always the cost of some real path to v, or infinity. It is never optimistic.
• dist[v] never increases. It only ever falls toward the true shortest distance.

So dist[v] is an upper bound that tightens. The whole game is proving that it reaches the true value, and that you can tell when it has.

3Dijkstra's algorithm

Repeatedly lock in the closest vertex you have not locked in yet. Everything else follows.

Dijkstra's insight is a claim about safety: the unfinished vertex with the smallest dist value already has its final answer. Nothing discovered later can improve it.

The implementation needs a container that hands back the smallest dist quickly, which is precisely the priority queue from Chapter 17.

import heapq

def dijkstra(graph, src):
    """graph: {vertex: [(neighbour, weight), ...]} with weight >= 0."""
    dist = {v: float("inf") for v in graph}
    prev = {v: None for v in graph}
    dist[src] = 0
    heap = [(0, src)]            # (best-known distance, vertex)
    done = set()

    while heap:
        d, u = heapq.heappop(heap)
        if u in done:            # a stale entry — we already finalised u
            continue
        done.add(u)              # LOCK IN: dist[u] is final from here on

        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))   # push, never decrease-key

    return dist, prev

Recovering the actual route uses the prev chain, exactly as in BFS:

def shortest_path(graph, src, dst):
    dist, prev = dijkstra(graph, src)
    if dist[dst] == float("inf"):
        return None, float("inf")      # unreachable
    path, cur = [], dst
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1], dist[dst]

4Where Dijkstra breaks

A single negative edge does not slow Dijkstra down. It makes it answer incorrectly, confidently, and without warning.

Here is the smallest counterexample worth memorising:

#        A --1--> B
#        |          |
#        4        (-3)
#        |          |
#        v          v
#        C <--------+
#
# True cheapest A -> C:  A -> B -> C  =  1 + (-3)  =  -2
# Dijkstra says:         4

graph = {"A": [("B", 1), ("C", 4)],
         "B": [("C", -3)],
         "C": []}

Trace it. Dijkstra pops A (0), relaxes to B = 1 and C = 4. The closest unfinished vertex is now B at 1, so B locks in and relaxes C to -2… but wait — walk the other order and it goes wrong: with C at 4 and B at 1, B is closer, so this tiny graph survives. Add one more vertex and it does not:

graph = {"A": [("B", 1), ("C", 2)],
         "C": [("D", 1)],
         "B": [("D", 100)],
         "D": [("B", -100)],   # a shortcut back, discovered too late
         }
# Dijkstra locks B in at 1, long before it learns about the -100 edge.
# Real answer for B: A -> C -> D -> B = 2 + 1 - 100 = -97.

And if a cycle has negative total weight, the question itself stops making sense: go round it again and the path gets cheaper, forever. There is no shortest path, only an infinite descent. Any correct algorithm must report that rather than return a number.

5Bellman-Ford

Stop being clever about the order. Relax every edge, V-1 times, and let correctness fall out of counting.

Dijkstra is fast because it is careful about which edge to relax next. Bellman-Ford gives that up entirely and relaxes all of them, over and over. What it buys is that it no longer needs the non-negativity assumption anywhere.

def bellman_ford(graph, src):
    """Returns (dist, prev), or (None, None) if a negative cycle is reachable."""
    dist = {v: float("inf") for v in graph}
    prev = {v: None for v in graph}
    dist[src] = 0
    edges = [(u, v, w) for u in graph for v, w in graph[u]]

    for _ in range(len(graph) - 1):          # V-1 rounds
        changed = False
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:                      # nothing improved: we are done early
            break

    for u, v, w in edges:                    # ONE extra round, as a test
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            return None, None                # still improving => negative cycle

    return dist, prev

That final loop is the part people skip and then miss. After V − 1 rounds nothing can legitimately improve. So if a V-th round still finds an improvement, the only possible explanation is a cycle you can go round to keep gaining — a negative cycle. The test costs one pass over the edges and turns a wrong answer into a reported failure.

6A*: Dijkstra with an opinion

Dijkstra explores in all directions equally, because it has no idea where the goal is. Tell it, and it stops wasting effort.

Dijkstra picks the vertex minimising g(v): the cost to reach it. A* picks the vertex minimising

f(v) = g(v) + h(v)

where h(v) is a heuristic: a guess at the remaining cost from v to the goal. That is the entire difference. The code is Dijkstra with one addition inside the push.

import heapq

def astar(graph, src, goal, h):
    """h(v) estimates the remaining cost from v to goal. Must never overestimate."""
    g = {v: float("inf") for v in graph}
    prev = {v: None for v in graph}
    g[src] = 0
    heap = [(h(src), src)]           # priority is f = g + h
    done = set()

    while heap:
        _, u = heapq.heappop(heap)
        if u in done:
            continue
        if u == goal:                # popping the goal IS the lock-in
            break
        done.add(u)

        for v, w in graph[u]:
            ng = g[u] + w
            if ng < g[v]:
                g[v] = ng
                prev[v] = u
                heapq.heappush(heap, (ng + h(v), v))   # <-- the only new part

    return g[goal], prev

Good heuristics are geometric or otherwise structural — they exploit something you know about the problem that the graph itself does not encode:

7Picking the right one

Five algorithms, five preconditions. The decision takes about ten seconds once you know what to ask.

Ask, in order: are any weights negative? do I need all pairs? is the graph acyclic? do I know where the goal is? are the weights only 0 and 1?

0-1 BFS deserves a mention because it is so cheap to write and so easy to miss. When every weight is 0 or 1, a plain deque replaces the heap: relax across a 0-edge and push the vertex to the front, relax across a 1-edge and push it to the back. The deque stays sorted by construction, so you get Dijkstra's answer at BFS's price.

from collections import deque

def zero_one_bfs(graph, src):
    """Every weight must be 0 or 1."""
    dist = {v: float("inf") for v in graph}
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)   # free: it belongs with the current layer
                else:
                    dq.append(v)       # costs 1: it belongs to the next layer
    return dist

>_Playground

All three algorithms on the same graph, then a negative edge that breaks one of them, then A* counting how much work it saved.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.