Dijkstra's Algorithm
dijkstra
Algorithms
Graph Algorithms (Core)
Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph algorithms power an enormous slice of real infrastructure, and almost all of them are short additions to a BFS or DFS skeleton you already wrote. **Graph Algorithms (Core)** covers that handful in detail. You will implement topological sort in two ways (Kahn's BFS-with-in-degree algorithm and the DFS-reverse-postorder algorithm), cycle detection on undirected graphs (DFS with parent tracking) and on directed graphs (DFS with white/gray/black coloring), Dijkstra's shortest-path algorithm with a min-heap and the relaxation invariant that makes it work, connected-component counting via DFS or Union-Find, and bipartite checking via two-color BFS. Along the way you will see why Dijkstra fails on negative edge weights, which motivates Bellman-Ford in the advanced lesson later. In **BFS & DFS (Intro)**, you wrote the two traversal skeletons. **Weighted Graph Representation** gave you the adjacency-list-of-tuples format that Dijkstra and friends actually consume. This lesson is where those primitives turn into named algorithms with clear use cases. From here, **Greedy (Intro)** introduces a different paradigm: instead of exploring every option, commit to the locally best choice at each step.
Not Started
0%
Practice Problems
Network Delay Time
Given a network of n nodes and weighted directed edges representing signal travel times, find the time it takes for a signal sent from node k to reach all nodes.
Code Snippets
Dijkstra Shortest Path Template
Dijkstra's algorithm finds the shortest path from a source to every reachable node in a weighted graph with non-negative edge weights. The textbook O((V + E) log V) implementation pairs a min-heap with a relaxation loop. This snippet covers the heap-based template, a parent-tracking variant that reconstructs the actual path, and an early-exit form for single-target queries.
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
Dijkstra and Shortest Paths
Decide between Dijkstra, Bellman-Ford, and 0/1 BFS, and trace Dijkstra on a small weighted graph. Code stems are Python.
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
Path with Maximum Probability
Find the path between two nodes that maximizes the product of edge success probabilities, via modified Dijkstra.
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.