Shortest Path Algorithms: Dijkstra's Algorithm

Graph Theory

Chapter 6 · Shortest Path Algorithms: Dijkstra's Algorithm

Every graph so far has been unweighted — Chapter 3's own finding-box already established that BFS finds the shortest path by edge count. Real-world graphs are usually weighted: a road has a distance, a network link has latency, a flight has a price. "Fewest edges" and "cheapest total weight" are genuinely different questions once weights enter the picture, and this chapter builds the algorithm that answers the second one.

Weighted Graphs: One Small Change to the Representation

A weighted graph attaches a number to every edge. The adjacency list from Chapter 2 barely changes — instead of storing just a neighbor, each entry stores a (neighbor, weight) pair: adj['A'] = [('B', 4), ('C', 1)] means A connects to B with weight 4 and to C with weight 1.

Dijkstra's Algorithm: Always Expand the Closest Unfinished Vertex

Dijkstra's algorithm is greedy: it repeatedly finalizes whichever not-yet-finalized vertex currently has the smallest known distance from the source, then uses that vertex to try to improve ("relax") the distances of its neighbors.

The mechanism

Keep a running distance table (source = 0, everything else = infinity) and a priority queue keyed by current known distance. Repeatedly pop the smallest-distance unfinished vertex, finalize it, then for each neighbor: if (finalized vertex's distance) + (edge weight) is smaller than the neighbor's current recorded distance, update it and push the neighbor back onto the queue.

Graph: A→B(4), A→C(1), C→B(2), B→D(1), C→D(5), D→E(3). Finding shortest distances from A:

Traced and verified directly

Pop A(0) → finalize A. Relax B: 0+4=4. Relax C: 0+1=1.
Pop C(1) → finalize C. Relax B: 1+2=3, which beats B's current 4 — update B to 3. Relax D: 1+5=6.
Pop B(3) → finalize B. Relax D: 3+1=4, which beats D's current 6 — update D to 4.
Pop D(4) → finalize D. Relax E: 4+3=7.
Pop E(7) → finalize E.
Final distances from A: {A:0, B:3, C:1, D:4, E:7}.

Notice B was updated twice — first to 4 (direct edge from A), then to a cheaper 3 once C was finalized and revealed the shorter route A→C→B. This is the entire point of the greedy strategy: finalize the closest vertex first, because nothing still in the queue can possibly offer it a cheaper route later — every other candidate is already at least as far away.

BFS Was Secretly Dijkstra All Along

Connecting back to Chapter 3

If every edge weight is exactly 1, Dijkstra's algorithm reduces exactly to Chapter 3's own BFS — the priority queue's "always pop the smallest distance" behavior becomes identical to a plain FIFO queue's "always process the next level," since every step increases distance by the same fixed amount. BFS is a special case of Dijkstra, not a separate idea.

Why It Breaks With Negative Weights

Dijkstra's greedy step assumes that once a vertex is finalized, nothing seen later can ever offer it (or anything already routed through it) a cheaper path. A negative edge weight breaks that assumption directly — a big negative edge discovered after a vertex has already been finalized can retroactively make an already-"settled" distance wrong, and Dijkstra never revisits a finalized vertex to fix it.

Graph: A→B(1), A→C(4), C→B(−10), B→D(100).

A verified counterexample

Dijkstra pops B(1) first (smaller than C's 4) and finalizes B at distance 1, immediately using it to set D's distance to 1+100=101. Only afterward does it pop C(4) and discover C→B=4−10=−6, a genuinely shorter route to B — but B is already finalized, so this correction never propagates onward to D. Dijkstra reports D=101. The true shortest A→D, found by checking every actual path, is 94 (via A→C→B→D = 4−10+100). Dijkstra's own final table even shows B=−6 — updated in the raw data even though the vertex was already "settled" — making the error easy to miss unless D is checked directly.

This is exactly why Dijkstra requires non-negative weights, and exactly the gap Chapter 7's own Bellman-Ford algorithm is built to close.

Real Relevance: Routing & Navigation

GPS and mapping software runs some form of Dijkstra (or a close relative) to find a shortest route by distance or time — road segments as edges, intersections as vertices, travel time or distance as weight. Network routers use a close cousin (OSPF/link-state routing) to find the cheapest path for data by latency and hop cost, with "cheapest" playing the same role weight plays here.

Dijkstra's Algorithm in Code

import heapq

def dijkstra(adj, source):
    dist = {v: float('inf') for v in adj}
    dist[source] = 0
    visited = set()
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue              # stale queue entry, already finalized
        visited.add(u)
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

roads = {
    'A': [('B',4), ('C',1)],
    'B': [('D',1)],
    'C': [('B',2), ('D',5)],
    'D': [('E',3)],
    'E': [],
}
print(dijkstra(roads, 'A'))  # {'A':0, 'B':3, 'C':1, 'D':4, 'E':7}

Hands-On Exercises

Exercise 1

Using Dijkstra's algorithm, trace the shortest distances from source P for the weighted graph: P→Q(2), P→R(9), Q→R(3), R→S(1). Show each pop-and-relax step, including any distance updates.

📄 View solution

Exercise 2

Explain, in terms of this chapter's own greedy assumption, why Dijkstra's algorithm never needs to reconsider a vertex once it has been popped and finalized — as long as every edge weight is non-negative.

📄 View solution

Exercise 3

This chapter's negative-weight counterexample showed Dijkstra reporting D=101 when the true shortest distance is 94, while the same run's final table showed B=−6, the actually-correct value. Explain why the algorithm ends up with a correct number for B but an incorrect one for D in the very same run.

📄 View solution

Chapter 6 Quick Reference

Weighted adjacency list: each entry is a (neighbor, weight) pair rather than just a neighbor
Dijkstra's algorithm: repeatedly finalize the closest unfinished vertex, then relax its neighbors' distances
BFS is exactly Dijkstra's algorithm when every edge weight is 1
Requires non-negative weights — a negative edge can retroactively invalidate an already-finalized distance, which Dijkstra never revisits
Real use: GPS/mapping route-finding and link-state network routing
Next chapter: Bellman-Ford — shortest paths that work with negative weights