← Shortest Paths · guided lesson
Shortest Paths
the story
Dijkstra's algorithm
Every tool here exists because something was too slow or broke without it. Here is what.
In 1956 Dijkstra needed a demo for the new ARMAC computer in Amsterdam that non-mathematicians could follow: the shortest route between two Dutch cities, on a reduced map of 64 cities. As he recalled in a 2001 interview, he designed it in about 20 minutes on a café terrace in Amsterdam, resting during a shopping trip with his fiancée — without pencil and paper. He published it three years later, in 1959, as "A note on two problems in connexion with graphs". Heap versions came later (O(E log V) by 1972; Fredman and Tarjan's Fibonacci heap in 1987) — that's what makes it fast on huge sparse graphs.
the problem it solved
The cheapest route from one place to every other place when every link has a non-negative cost — in time only a little more than the size of the map.
why it matters: without it
Routing would fall back to Bellman–Ford's V·E work, or to trying routes one by one — in the worst case a single city-to-city query on a big map could take hours instead of moments.
sources: Dijkstra — A note on two problems in connexion with graphs (Numerische Mathematik, 1959) ↗ · Frana & Misa — An interview with Edsger W. Dijkstra (CACM, 2010; recorded 2001) ↗ · Schrijver — On the history of the shortest path problem (Documenta Mathematica, 2012) ↗ · Fredman & Tarjan — Fibonacci heaps and their uses in improved network optimization algorithms (JACM, 1987) ↗
also in this chapter: Bellman–Ford (edge relaxation in rounds) · Floyd–Warshall (all pairs) · 0-1 BFS (deque instead of heap) · Minimax (bottleneck) paths
the idea
The idea in 30 seconds
BFS finds the path with the fewest edges. With weights, a 3-edge route can be cheaper than a 1-edge route, so BFS gives wrong answers.
Dijkstra fixes this by always expanding the closest unfinished node next — a priority queue replaces BFS's plain queue.
Negative weights break Dijkstra's promise; Bellman–Ford handles them by relaxing every edge, round after round.
picture this
A packet leaves your laptop in Kolkata for a server in Mumbai, and every router-to-router link has a cost. An OSPF router computes routes exactly like Dijkstra: settle the cheapest router first, then use it to reach the next cheapest. Costs never go negative, so a settled cost can never be beaten later.
watch it
Dijkstra step by step
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Dijkstra step by step
Watch the priority queue: the smallest entry is polled, its edges relaxed, and stale entries skipped. Green edges form the shortest-path tree.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Bellman–Ford relaxation rounds
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Bellman–Ford relaxation rounds
The default graph has negative edges. Each round fixes paths one edge longer; a quiet round means we can stop early.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Relaxation is the one move every algorithm here shares: if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;. They only differ in which order they relax edges.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Dijkstra (weights ≥ 0): poll the smallest {dist, node} from a PriorityQueue; that distance is final. O((V + E) log V).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Lazy deletion: Java's PriorityQueue can't lower a key, so push a new entry and skip stale ones with if (d > dist[u]) continue;.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Bellman–Ford (negative weights OK): relax all E edges, V − 1 times. If a V-th round still improves something, there is a negative cycle. O(V·E).
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Bellman–Ford with k rounds = cheapest path using at most k edges (copy the array each round). That's exactly LC 787.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Floyd–Warshall: all pairs in O(V³) with three loops — the middle stop k must be the outer loop.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
0-1 BFS: weights are only 0 or 1 → use an ArrayDeque, 0-edges to the front, 1-edges to the back. O(V + E), no heap.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Many grid problems are shortest paths in disguise. If the "cost" of a path is its max step (not the sum), Dijkstra still works — it's a minimax path.
spot the pattern
When you see this, think this
"Minimum cost / time / distance" with weighted edges
Dijkstra (if no negative weights)
"At most k stops / k edges"
Bellman–Ford with k + 1 rounds, or BFS by levels
Negative weights, or "detect an arbitrage / negative cycle"
Bellman–Ford (or Floyd–Warshall's diagonal)
"Every pair", "for each city count reachable cities", n ≤ 100
Floyd–Warshall
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Running Dijkstra with negative edges. The visited-set version silently returns wrong answers; the lazy version loses its time guarantee.
- Forgetting the stale check
if (d > dist[u]) continue;— still correct, but the run can blow up to far more work.
quick check
One question. No pressure.
Edges 0→1 (10), 0→2 (1), 2→1 (1). What does BFS (fewest edges) give for node 1, and what is the true shortest distance?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Network Delay Time
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What does "relaxing" edge u → v mean?
Question 1: What does "relaxing" edge u → v mean?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.