Graph Algorithms
graph-algorithms
Code Snippets
Dijkstra in Python with heapq
Dijkstra finds the shortest path in a weighted graph with non-negative edge weights. The Python idiom is `heapq` (a binary min-heap) plus a distance dict, which gives O((V + E) log V) without external libraries. This entry covers the standard single-source template, path reconstruction, and the early-exit shortest-path-to-one-target variant.
Question Banks
Graph Theory Essentials
Interview-grade prompts on BFS/DFS, shortest paths, connectivity, and cycle detection across directed and undirected graphs.
System Design
Design Google Maps
Design Google Maps: a global mapping service that renders the Earth from 256x256 tiles, computes the shortest driving route in under 200 ms, and folds live traffic into routing for 1B users issuing 5B route requests per day. The interview centerpiece is the routing engine: how Dijkstra is too slow on a continent-scale graph and how Contraction Hierarchies (CH) precompute shortcuts so the live query is logarithmic. We cover the tile pyramid (zoom 0-20, ~1 trillion possible tiles at zoom 20), how live traffic from 100M Android phones updates edge weights every minute, and how to keep navigation latency under 1 second when re-routing.
Community
Graph Algorithms 101
Why most production graph work is modeling, not algorithm; the two traversals you actually use; and the representation table that drives every memory tradeoff.
Union-Find Explained with Three Real Problems
Disjoint-set union seen through Kruskal MST, dynamic connectivity in a message bus, and grid percolation, plus when the path-compression-plus-rank optimization stops being optional.
Dijkstra vs Bellman-Ford vs Floyd-Warshall: Pick One
Three shortest-path algorithms, three honest decision criteria. When negative weights matter, when all-pairs is worth O(V^3), and why Dijkstra is the default for a reason.
Topological Sort, Three Ways I Have Actually Used It
Build-system DAGs, course-prereq UI ordering, microservice startup choreography. Three production stories from the same Kahn's algorithm boilerplate.