Shortest Paths & Minimum Spanning Trees
The problem
Two of the most common real questions about a weighted graph — 'what's the cheapest way to get from A to B' and 'what's the cheapest set of edges connecting everything' — need dedicated algorithms, because generic BFS/DFS traversal doesn't account for edge weights at all.
Why now
Graph algorithms already gave BFS as unweighted shortest path; Dijkstra is the direct generalization to weighted edges, and it needs heaps-and-priority-queues to always expand the cheapest known frontier efficiently. Minimum spanning tree algorithms solve a related but distinct problem, and Kruskal's specifically needs union-find to detect cycles cheaply while building the tree.
Mental model
Dijkstra is BFS with a priority queue instead of a plain queue — always expand whichever reachable node currently has the cheapest known total distance, exactly generalizing 'explore the nearest unvisited node' to weighted edges. A minimum spanning tree connects every node as cheaply as possible with no cycles; Kruskal's greedily adds the cheapest edge that doesn't create a cycle (checked via union-find), while Prim's grows one connected tree greedily outward (checked via a priority queue) — two different greedy strategies, both provably optimal for this specific problem.
Requires
- Graph AlgorithmsComputer Science Fundamentals
Both Dijkstra's algorithm and MST algorithms are direct extensions of the graph traversal machinery (BFS's frontier-expansion idea) already covered, adapted specifically to handle edge weights.
- Heaps & Priority QueuesComputer Science Fundamentals
Dijkstra's core operation — always expand the cheapest known frontier node next — requires a priority queue to be efficient; without it, finding the minimum each step degrades to a slow linear scan.
- Union-Find (Disjoint Set)Computer Science Fundamentals
Kruskal's MST algorithm needs to detect, cheaply and repeatedly, whether adding an edge would create a cycle — exactly the question union-find is built to answer in near-constant time.
Used in
- GPS navigation and network routing protocols computing shortest paths
- Network design problems minimizing total cable/connection cost (MST)
- Flight or transit route planning with weighted connections
- Approximation algorithms for harder problems (e.g. traveling salesman) that start from an MST
Projects
- Implement Dijkstra's algorithm using a priority queue and trace it by hand on a small weighted graph to confirm the shortest-path distances
- Implement Kruskal's algorithm using union-find to compute a minimum spanning tree, and verify the total weight is minimal by comparison to a brute-force check on a small graph
Examples
- Dijkstra's algorithm computing shortest routes from one city to all others is the same core idea Google Maps uses, generalized further with real-time traffic weights
- Kruskal's algorithm sorts all edges by weight and greedily adds each one unless union-find reports its endpoints are already connected, which would create a cycle
Resources
Mastery checklist
- I can implement Dijkstra's algorithm using a priority queue
- I can implement Kruskal's or Prim's algorithm for minimum spanning tree
- I can explain why Dijkstra's algorithm fails on graphs with negative edge weights
- I can choose the correct algorithm (Dijkstra vs. MST) for a given weighted-graph problem