Day 21 — Shortest Paths
You have a graph. Some weights on the edges (or not). You want to know the cheapest way to get from A to Z — or from A to everywhere, or from everywhere to everywhere.
That single question — “what’s the shortest path?” — fans out into four algorithms with wildly different costs, assumptions, and use cases. Pick the wrong one and you’ll either get the wrong answer (Dijkstra on a graph with negative edges) or take a hundred times longer than necessary (Floyd-Warshall on a sparse road network).
This chapter is about knowing which lever to pull when the interviewer says “find the shortest path.”
What you’ll learn today
- The shortest-path landscape — single-source vs all-pairs, weighted vs unweighted, negative weights, cycles
- BFS on unweighted graphs — the simplest case,
O(V + E), every edge has implicit weight 1 - Dijkstra’s algorithm — the workhorse,
O((V + E) log V)with a min-heap, handles non-negative weights - Bellman-Ford —
O(V · E), slower but handles negative edges and detects negative cycles - Floyd-Warshall —
O(V³), all-pairs in a triple loop, devastatingly simple to code - The decision matrix — given a graph, what should you reach for first?
- Eight interview classics — network delay, cheapest flights, minimum effort, binary matrix BFS, word ladder, and more
Half of “graph problem” interview questions are shortest-path problems in disguise. “Find the minimum cost path.” “Reach the target in the fewest moves.” “What’s the closest cell with property X?” If the answer is a path through a graph and “shortest” or “cheapest” is in the question, one of the four algorithms in this chapter is the answer.
Roadmap
- Introduction — the shortest-path problem, single-source vs all-pairs, what edge weights mean, and the relaxation idea every algorithm in this chapter is built on.
- BFS on Unweighted Graphs — the simplest shortest path: every edge has weight 1, plain breadth-first search finds the answer in
O(V + E). - Dijkstra’s Algorithm — the priority-queue greedy. The one shortest-path algorithm everyone needs to memorize cold.
- Bellman-Ford — slower, but handles negative edges and detects negative cycles. The only algorithm that does the second.
- Floyd-Warshall —
O(V³)dynamic programming for all-pairs shortest paths. Five lines of code; surprisingly powerful. - Picking the Right Algorithm — the decision tree. Given a graph and a question, which algorithm wins?
- Basic Questions — warm-ups: hand-trace Dijkstra, identify negative cycles, count relaxations.
- Practice Questions — eight interview problems covering every shape in the chapter.
Shortest paths build on Graphs (Basics), DFS and BFS, and Heaps. Bellman-Ford has a flavor of Dynamic Programming (it’s basically DP on path length). Floyd-Warshall is dynamic programming on intermediate vertices. If any of those feel shaky, revisit the chapter first.
Coming up: Day 22 — Minimum Spanning Trees, where greedy beats DP and Union Find returns to the spotlight.