Further Reading: Weighted Graphs and Shortest Paths

Annotated pointers for going deeper. Start with the textbook sections that re-present this chapter's algorithms with more drill, then branch toward the topics that interest you: the correctness proofs, the goal-directed search (A*) behind real navigation, or the routing protocols that run these algorithms at internet scale.

Core textbook treatments

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapters 22–23 (single-source and all-pairs shortest paths) The definitive reference for everything in this chapter: relaxation, Dijkstra, Bellman-Ford, and Floyd-Warshall, each with a full correctness proof in the same invariant style as §29.3. If you want the rigorous version of every claim here — including the path-relaxation property stated and proved — this is the source.

Rosen, Discrete Mathematics and Its Applications (8th ed.), §10.6 (shortest-path problems) The market-standard discrete-math treatment of Dijkstra and weighted graphs, with a large, well-graded exercise bank. Lighter on Bellman-Ford and the proofs than CLRS, but excellent for additional hand-trace practice.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the graph-theory chapters Freely available. The most CS-flavored development of graphs and their algorithms, in the same "motivate the algorithm before formalizing it" spirit as this chapter. A strong companion if the proofs in §29.3–29.4 felt fast.

West, Introduction to Graph Theory (2nd ed.) The mathematician's view of weighted graphs and paths. Reach for it when you want the graph-theoretic context (cycles, trees, connectivity) underneath the algorithms, rather than the implementation.

On the correctness proofs

CLRS (4th ed.), §22.3 (Dijkstra) and §22.1 (the Bellman-Ford / relaxation lemmas) Read these alongside §29.3 and §29.4. CLRS isolates the reusable lemmas — the "upper-bound property" (our safety of relaxation), the "convergence property," and the "path-relaxation property" — and the Dijkstra proof there is the same contradiction-and-invariant argument, written for a general audience.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the graph chapters Freely available. A gentle, proof-forward open textbook. Good for re-deriving the optimal-substructure fact (a shortest path is made of shortest paths) slowly, which is the quiet engine behind every proof in this chapter.

Goal-directed search and navigation

Hart, Nilsson & Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics (1968) Tier 2 — the original A* paper. The source of the algorithm §29.6 describes as "Dijkstra plus an admissible heuristic." Read it after you are comfortable with Dijkstra's correctness, to see admissibility (the heuristic never overestimates) doing exactly the job non-negativity did in §29.3. Widely reprinted and summarized; the core idea is the priority key $f(v) = g(v) + h(v)$.

Red Blob Games, "Introduction to A* / Amit's A* Pages" (redblobgames.com) Free online. The clearest interactive visual explanation of BFS, Dijkstra, and A* side by side, with animations of exactly the "expanding circle vs. goal-directed" contrast Case Study 1 analyzes by hand. The best single resource for seeing why A* explores less.

Routing at internet scale

Kurose & Ross, Computer Networking: A Top-Down Approach, the network-layer / routing chapter Tier 2. The standard networking textbook's treatment of link-state (OSPF, which runs Dijkstra) and distance-vector (RIP, which is distributed Bellman-Ford) routing — the two real protocols §29.6 maps onto this chapter's two algorithms, including the count-to-infinity problem as a distributed-Bellman-Ford phenomenon.

Tools and practice

networkx documentation — shortest-path functions (dijkstra_path, bellman_ford_path, floyd_warshall, astar_path) Free online. The production Python library implementations of every algorithm in this chapter. Use it to check your hand-rolled versions on larger graphs — after you have implemented them from scratch, as the chapter insists. Reading its source is also an education in lazy deletion and predecessor recovery.

The OEIS and small graph datasets (e.g., the road-network and social-graph samples bundled with networkx) Free. Real graphs to run your dijkstra and bellman_ford against. A good source of "conjecture and test, then prove" material for the Part F exercises — find a pattern on real data, then prove it.

Suggested order

  1. Re-read §§29.1–29.4 here, then do Rosen §10.6 exercises for additional Dijkstra drill.
  2. Read CLRS Ch. 22 (especially §22.3) for the full, rigorous correctness proofs that §29.3 sketches.
  3. Explore the Red Blob Games A* pages, then skim the Hart–Nilsson–Raphael paper, to deepen §29.6 and Case Study 1.
  4. Read the Kurose–Ross routing chapter to connect the algorithms to OSPF and RIP.
  5. Save CLRS Ch. 23 (all-pairs, Floyd-Warshall and Johnson's algorithm) for when you want the all-pairs picture in full, including correct re-weighting of negative edges.