Shortest Paths

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Relax an edge: if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;. Every algorithm here is relaxation in a different order.

   #1
2. ↯use it when

   Weights ≥ 0 → Dijkstra. Negative or "at most k edges" → Bellman–Ford. All pairs, V ≤ ~400 → Floyd–Warshall. Only 0/1 → 0-1 BFS.

   #2
3. { }template

   Heap of {dist, node}: poll → if (d > dist[u]) continue; → relax every edge → push each improved {dist[v], v}.

   #3
4. O( )cost

   Dijkstra O((V + E) log V) · Bellman–Ford O(V·E) · Floyd O(V³) · 0-1 BFS O(V + E) · plain BFS O(V + E) when all edges cost the same.

   #4
5. !trap

   Dijkstra + a negative edge = wrong answers. "Polled means final" only holds when no edge can shrink a path later.

   #5
6. !trap

   (a, b) -> a[0] - b[0] can overflow and Integer.MAX_VALUE + w wraps negative. Use Integer.compare; check ∞ before adding.

   #6
7. !trap

   Floyd–Warshall: the middle stop k is the OUTER loop. K-stops Bellman–Ford: clone the array each round.

   #7
8. ✦pro tip

   Path cost is a max (effort, water level) or a product ≤ 1? Same Dijkstra — swap + for max or ×, keep the heap.

   #8
9. ✦pro tip

   Target known? Return when it is polled, not when it is first pushed.

   #9

Shaky on a card? Open the chapter or flip its recall cards.