Three graph questions require different evidence: which task may happen next, which route is cheapest from a source, and which connections join a network at minimum total cost? A traversal alone does not answer all three.
Reading route¶
DAGs and topological order: remove satisfied dependencies with Kahn’s algorithm.
Shortest paths and relaxation: distinguish tentative distances from final answers.
Dijkstra and lazy heaps: settle vertices under nonnegative edge weights.
Shortest paths in a DAG: relax in dependency order, including negative weights.
Spanning trees and safe edges: define the objective and justify greedy choices.
Prim’s algorithm: grow one component at a time with a frontier of edges.
Kruskal’s algorithm: scan globally sorted edges and reject cycles.
Compare the graph objectives: select an algorithm by the required result.
Read graph representations, BFS and DFS and priority queues first. Before the Kruskal code, read Topic 12: union–find; its full implementation is kept there rather than duplicated here. Topic 9 is a separate spatial-search branch and is not a prerequisite.
The examples follow the Week 12–13 lecture graphs. All graph keys include sinks and isolated vertices. Weighted code assumes finite numeric edge weights, consistent adjacency lists and bounded-cost arithmetic; Dijkstra additionally checks for negative weights. String labels are used in the traces, and None denotes a missing predecessor.
Read each method through the same questions¶
Each algorithm page states its objective, input/return/error contract, working state, next-step invariant, trace, code context, implementation choices and costs. Compare the meaning of a queue entry, heap key or parent map before reusing an earlier implementation.
The comparison table separates working storage from returned state and covers ties, empty/disconnected graphs and unsupported weights/cycles. Imports are explicit where possible; DAG paths reuses Kahn and Kruskal reuses Topic 12’s class, with those dependencies linked beside the code. Negative-cycle route algorithms, directed-cycle witnesses and SCC implementations remain future extensions.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.