27

Shortest Paths

When edges have weights, the fewest hops is not the cheapest route. Dijkstra, Bellman–Ford and friends fix that.

intermediate~70 min5 simulations9 problems

▶ guided lesson⚡ 1-minute summary↻ 13 recall cards

before this: Graphs · Heaps

01 · why it exists

Why this exists, and the weight it carries

since1956 (idea) · 1959 (paper)

Dijkstra's algorithm

Edsger W. Dijkstra

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 solvedThe 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.

its jobs today

  • Internet routing: an OSPF router computes its shortest-path tree with itself as the root using Dijkstra (RFC 2328, §16.1).
  • Maps and games: route planners and A path-finding are Dijkstra with extras — A adds a "distance left" hint to the heap order.
  • Any "cheapest / fastest / most reliable" question on a network with non-negative costs — including the minimax and probability variants in this chapter.

the weight it carries

Illustrative: a road map with 10 lakh junctions (V = 10⁶) and 25 lakh roads (E = 2.5·10⁶). Heap Dijkstra ≈ (V + E) · log₂ V ≈ 3.5·10⁶ × 20 = 7·10⁷ steps. Bellman–Ford: V · E = 2.5·10¹² relaxations — about 36,000× more.

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.

when · why · how

when
A weighted graph, every weight ≥ 0, one source (or one source–target pair).
why
The closest unsettled node can't be improved later: every other route already costs at least as much, and edges never subtract. O((V + E) log V) with a binary heap, versus O(V · E) for Bellman–Ford.
how
PriorityQueue<int[]> of {dist, node} compared with Integer.compare; poll, skip when d > dist[u], relax, push. Switch to long[] when sums can pass 2·10⁹.

02 · plain english

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.

03 · remember

What you must know

  • 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.
  • Dijkstra (weights ≥ 0): poll the smallest {dist, node} from a PriorityQueue; that distance is final. O((V + E) log V).
  • 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;.
  • 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).
  • Bellman–Ford with k rounds = cheapest path using at most k edges (copy the array each round). That's exactly LC 787.
  • Floyd–Warshall: all pairs in O(V³) with three loops — the middle stop k must be the outer loop.
  • 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.
  • 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.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

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.

loading simulation…
sim

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.

loading simulation…
sim

Floyd–Warshall matrix

Each round allows one more node as a middle stop. The violet row and column supply every candidate path in that round.

loading simulation…
sim

0-1 BFS on a grid

Free cells jump to the front of the deque, obstacles go to the back. The deque stays sorted without a heap.

loading simulation…
sim

Minimax Dijkstra on a height map

Same heap, new combine step: a route costs its worst climb, max(e, step), not the sum. The goal's first poll is the answer.

loading simulation…

05 · cost

Time & space, explained

Single-source shortest paths
TimeSpaceWeightswhy
BFSO(V + E)O(V)all equalEach node and edge is handled once. Only correct when every edge costs the same.
0-1 BFS (deque)O(V + E)O(V)0 or 1A node is pushed at most twice; the deque never needs sorting.
Dijkstra, binary heap (lazy)O((V + E) log V)O(V + E)≥ 0Up to E pushes and polls, each O(log E) = O(log V) because E ≤ V².
Dijkstra, plain arrayO(V²)O(V)≥ 0V rounds, each scans all V nodes for the minimum. Wins on dense graphs (E ≈ V²).
Bellman–FordO(V · E)O(V)any (detects negative cycles)V − 1 rounds × E relaxations. Early exit when a round changes nothing.
Bellman–Ford, k roundsO(k · (V + E))O(V)anyk rounds, each relaxing all E edges and copying dist (O(V)) so a round can't chain more than one new edge.
All pairs and extras
TimeSpacewhy
Floyd–WarshallO(V³)O(V²)Three nested loops over V; one V × V matrix updated in place.
Dijkstra from every nodeO(V · (V + E) log V)O(V + E)V independent Dijkstra runs. Beats Floyd on sparse graphs.
Path reconstructionO(path length)O(V)Store parent[v] when relaxing; walk back from the target and reverse.
Binary search on answer + BFS (grids)O(mn · log R)O(mn)log R guesses (R = value range), each a full O(mn) BFS.

06 · java

Raw vs Collections Framework

Dijkstra: plain arrays vs PriorityQueue

javaO(V²) array versionjava.util.*
class DijkstraArray {    /** O(V²) Dijkstra with plain arrays: no heap, scan for the closest unfinished node. */    static int[] shortest(int n, int[][] edges, int src) {        int[][] w = new int[n][n];        for (int[] row : w) Arrays.fill(row, -1);              // -1 = no edge        for (int[] e : edges)            if (w[e[0]][e[1]] == -1 || e[2] < w[e[0]][e[1]]) w[e[0]][e[1]] = e[2];         int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        boolean[] done = new boolean[n];        dist[src] = 0;        for (int round = 0; round < n; round++) {            int u = -1;                                          // closest unfinished node            for (int v = 0; v < n; v++)                if (!done[v] && dist[v] != Integer.MAX_VALUE && (u == -1 || dist[v] < dist[u])) u = v;            if (u == -1) break;                                  // the rest is unreachable            done[u] = true;                                      // dist[u] is now final            for (int v = 0; v < n; v++)                if (w[u][v] >= 0 && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];        }        return dist;    }}
  • The heap version is the default interview answer: O((V + E) log V) on sparse graphs.
  • Store int[] {dist, node} in the heap, compare with Integer.compare(a[0], b[0]) — never a[0] - b[0], which can overflow.
  • PriorityQueue has no decrease-key. Push a fresh entry instead and skip it later when d > dist[u] (lazy deletion).
  • The array version needs no heap at all and is O(V²) — better when the graph is dense, or V is tiny.
  • Use long distances when weights × path length can pass ~2.1·10⁹ (LC 1976 has weights up to 10⁹).

Rebuild the actual path

javaparent[] + walk backjava.util.*
class PathReconstruction {    /** Dijkstra that also remembers parent[v] = the node we came from; then walks back. */    static List<Integer> path(int n, int[][] edges, int src, int target) {        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());        for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});         int[] dist = new int[n];        int[] parent = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        Arrays.fill(parent, -1);        dist[src] = 0;        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));        pq.offer(new int[] {0, src});        while (!pq.isEmpty()) {            int[] top = pq.poll();            int d = top[0], u = top[1];            if (d > dist[u]) continue;            for (int[] next : adj.get(u)) {                if (d + next[1] < dist[next[0]]) {                    dist[next[0]] = d + next[1];                    parent[next[0]] = u;                          // best way into next[0] is via u                    pq.offer(new int[] {dist[next[0]], next[0]});                }            }        }        if (dist[target] == Integer.MAX_VALUE) return List.of();  // unreachable        List<Integer> path = new ArrayList<>();        for (int v = target; v != -1; v = parent[v]) path.add(v); // target → … → src        Collections.reverse(path);        return path;    }}
  • Whenever dist[v] improves, set parent[v] = u. The parents form a tree rooted at the source.
  • Walk from the target to the source through parent, then Collections.reverse — O(path length).
  • If dist[target] is still ∞, there is no path: return an empty list.

Bellman–Ford (negative edges, negative cycles)

javaV − 1 rounds + 1 checkjava.util.*
class BellmanFord {    /** Works with negative edges. Returns null if a negative cycle is reachable from src. */    static int[] shortest(int n, int[][] edges, int src) {        int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[src] = 0;        for (int round = 1; round <= n - 1; round++) {            boolean changed = false;            for (int[] e : edges) {                int u = e[0], v = e[1], w = e[2];                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {                    dist[v] = dist[u] + w;                    changed = true;                }            }            if (!changed) break;        }        for (int[] e : edges)            if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) return null;        return dist;    }}
  • Just an edge list — no adjacency list needed. int[][] edges is enough.
  • Guard dist[u] != Integer.MAX_VALUE before adding, or MAX_VALUE + w overflows into a negative number.
  • Only negative cycles reachable from the source are detected. That's usually what you want.

Floyd–Warshall (all pairs)

javathree loops, k outsidejava.util.*
class FloydWarshall {    static final int INF = 1_000_000_000; // "no path yet" — never added to, see the guards     /** All-pairs shortest paths (negative edges OK). dist[i][i] < 0 afterwards ⇔ i is on a negative cycle. */    static int[][] allPairs(int n, int[][] edges) {        int[][] dist = new int[n][n];        for (int[] row : dist) Arrays.fill(row, INF);        for (int i = 0; i < n; i++) dist[i][i] = 0;        for (int[] e : edges) dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);        for (int k = 0; k < n; k++)            for (int i = 0; i < n; i++) {                if (dist[i][k] == INF) continue;              // i can't reach k                for (int j = 0; j < n; j++)                    if (dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])                        dist[i][j] = dist[i][k] + dist[k][j];            }        return dist;    }}
  • Use a big sentinel like 1_000_000_000 and skip ∞ cells, so ∞ + negative never fakes a path.
  • After the loops, dist[i][i] < 0 means node i sits on a negative cycle.
  • Practical up to V ≈ 400 (64 million steps). For bigger sparse graphs, run Dijkstra from each node.

0-1 BFS with ArrayDeque

javadeque instead of heapjava.util.*
class ZeroOneBfs {    /** Every weight is 0 or 1: a deque replaces the heap. 0-edges go to the front, 1-edges to the back. */    static int[] shortest(int n, int[][] edges, int src) {        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());        for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});         int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[src] = 0;        Deque<Integer> deque = new ArrayDeque<>();        deque.offerFirst(src);        while (!deque.isEmpty()) {            int u = deque.pollFirst();            for (int[] next : adj.get(u)) {                int v = next[0], w = next[1];                if (dist[u] + w < dist[v]) {                    dist[v] = dist[u] + w;                    if (w == 0) deque.offerFirst(v); // same distance → front                    else deque.offerLast(v);         // one more → back                }            }        }        return dist;    }}
  • offerFirst for 0-weight edges, offerLast for 1-weight edges, always pollFirst.
  • The deque only ever holds two distance values, D and D + 1, in order — so the front is always the minimum.
  • Use ArrayDeque, not LinkedList (faster) and never Stack.
Java API you will actually use
calldoescost
new PriorityQueue<int[]>((a, b) -> Integer.compare(a[0], b[0]))Min-heap of {dist, node} pairsO(1) to create
pq.offer(e) / pq.poll()Push / remove the smallestO(log n)
pq.peek()Look at the smallest without removingO(1)
pq.remove(obj)Remove an arbitrary entry (avoid — that's why we use lazy deletion)O(n)
deque.offerFirst(x) / offerLast(x) / pollFirst()0-1 BFS operations on ArrayDequeO(1) amortized
Arrays.fill(dist, Integer.MAX_VALUE)Mark every node unreachedO(V)
dist.clone()Snapshot for round-limited Bellman–FordO(V)
Comparator.comparingInt(a -> a[0])Same comparator, more readableO(1)

Unweighted graph / every edge costs the same

→ Plain BFS with ArrayDeque

O(V + E); a heap would only add a log factor.

Weights are only 0 and 1

→ 0-1 BFS with ArrayDeque

O(V + E) and no heap.

Non-negative weights, one source

→ Dijkstra with PriorityQueue<int[]>

O((V + E) log V) — the workhorse.

Negative edges, or "at most k edges"

→ Bellman–Ford (copy the array each round for the k-limit)

Dijkstra's "polled = final" promise breaks with negative edges.

Distances between all pairs, V ≤ ~400

→ Floyd–Warshall on int[V][V]

Tiny code, O(V³), handles negative edges.

Path cost = max (or min) edge, not sum

→ Dijkstra with max() instead of +, or binary search + BFS, or union-find

Minimax paths still have the "finalized when polled" property.

07 · recognise

Spot the pattern

"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

Costs are 0 or 1 ("free if you follow the arrow", "remove an obstacle")

0-1 BFS with a deque

Grid where a path's cost is its largest step / highest cell

Minimax Dijkstra, or binary search the answer + BFS, or union-find

Maximise a product of probabilities ≤ 1

Dijkstra with a max-heap (multiplying by ≤ 1 never helps, like adding ≥ 0)

"Number of shortest paths"

Dijkstra + a ways[] array updated on ties

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • 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.
  • Comparator (a, b) -> a[0] - b[0] overflows on large values. Use Integer.compare / Long.compare.
  • Integer.MAX_VALUE + w wraps to a negative number. Check for ∞ before adding, or use a smaller sentinel like 10⁹.
  • Floyd–Warshall with k as the inner loop — the results are wrong. k (the middle stop) must be the outermost loop.
  • LC 787 with plain Bellman–Ford updating in place: one round can chain several edges, breaking the k-stop limit. Copy the array each round.
  • Marking a node visited when it is pushed in standard Dijkstra. A cheaper route may arrive later; finalize on poll.
  • Using int when sums can exceed 2³¹ − 1 — LC 1976 needs long.

tricks

  • Say "relax" out loud: "I relax edge u→v: if going through u is cheaper, update v and push it." Interviewers recognise it instantly.
  • Before coding, ask: weighted? negative weights? one source or all pairs? limit on edges? The answers pick the algorithm.
  • Memorise one Dijkstra template (the one in this chapter) and adapt it: the combine step (+, max, ×) and the heap order are the only knobs.
  • Grids: treat each cell as a node r * cols + c or keep {cost, r, c} arrays in the heap. 4 directions → E ≈ 4·V.
  • If the destination is known, return as soon as it is polled — not when it is first pushed.
  • Chalo, dry-run karte hain — on a 4-node graph where the direct edge is expensive (0→3 costs 10, 0→1→2→3 costs 3). It catches most bugs.

09 · why & how

Questions you might be too shy to ask

Why can't I just use BFS on a weighted graph?

BFS finishes nodes in order of edge count. A direct road of length 100 is found before a 3-road route of total length 3, and BFS never revisits it. Dijkstra finishes nodes in order of total distance instead — that's the whole difference.

Why does the heap hold {dist, node} pairs and not just the node?

A PriorityQueue places an entry by its key at the moment it is pushed. If you push only node and compare by dist[node], that key changes later while the node sits inside — the heap does not re-sort itself, so poll() can hand you the wrong node. Storing the distance inside the entry freezes the key. That's also why an older, bigger copy can go stale and must be skipped.

Why does Dijkstra break with negative edges?

Dijkstra assumes that once the closest node is polled, no other route can be shorter — every other route already costs at least as much and can only grow. A negative edge lets a route shrink later. Example: 0→1 (2), 0→2 (5), 2→1 (−4), 1→3 (1). The visited-set version finalizes node 1 at 2 and node 3 at 3, but 0→2→1→3 costs 2. The lazy version may re-process nodes and patch this up, but then its O((V + E) log V) guarantee is gone (worst case exponential). Use Bellman–Ford.

What is a negative cycle, and why does it break "shortest"?

A loop whose edges add up to less than 0 — like 1→2 (3), 2→1 (−5): one round trip costs −2. Go around again and the route gets cheaper again, forever. So nothing reachable from that loop has a shortest route; the honest answer is "−∞". That's why Bellman–Ford reports the cycle instead of a number. Dhyan do: in an undirected graph, one negative edge u–v is already a negative cycle (u→v→u).

Can't I just add a big number to every edge so nothing is negative?

No — it punishes routes that use more edges. Example: 0→1 (−2) then 1→2 (−2) costs −4; the direct 0→2 (−3) costs −3. The 2-edge route wins. Add 3 to every edge: the 2-edge route becomes 1 + 1 = 2, the direct one 0. Now the wrong route wins. Each route pays +3 per edge, not +3 once, so the ranking of routes changes.

Why lazy deletion instead of updating the entry in the heap?

PriorityQueue.remove(obj) is O(n), and there is no decrease-key. Pushing a duplicate is O(log n). The old entry stays, and when it's polled we see d > dist[u] and skip it. The heap can hold about E entries, so each operation is O(log E) — and since E ≤ V², log E ≤ 2 log V, which is still O(log V).

Why must k be the outer loop in Floyd–Warshall?

Round k means "shortest paths that may only stop at nodes 0..k in the middle". Round k needs round k − 1 fully finished for every pair. With k inside, you would combine paths that aren't ready yet.

When should I pick Bellman–Ford over Dijkstra?

Three cases: negative edge weights, detecting a negative cycle, or a limit on the number of edges ("at most k stops"). Otherwise Dijkstra is much faster.

Why does 0-1 BFS work without a heap?

When you pop a node at distance D, a 0-edge creates distance D (goes to the front) and a 1-edge creates D + 1 (goes to the back). So the deque only ever contains D's followed by D + 1's — already sorted. The front is always the minimum, just like a heap would give you.

Swim in Rising Water marks a cell seen when it is pushed. Isn't that the pitfall?

It is safe there for one reason: the price of entering a cell is its own height — the same from every side. Polls come out in non-decreasing order, so a later route into that cell costs max(t', h) ≥ max(t, h), never less than the first push. In Path With Minimum Effort the step |Δh| depends on which neighbour you came from, so a later route can be cheaper. There, finalize on poll. Not sure? Use the safe template: relax, push, skip stale entries.

Can I find the longest path by putting a max-heap in Dijkstra?

No. A detour can always make a path longer, so "polled = final" breaks — the first time you settle a node is not its longest route. For a general graph, the longest simple path has no known fast algorithm (it is NP-hard). On a DAG it is easy: go in topological order and take max instead of min — see Topological Sort. Path with Maximum Probability is different: multiplying by ≤ 1 never helps, so Dijkstra's promise still holds.

Is Dijkstra greedy or dynamic programming?

Both views are fair. It greedily picks the closest node; the update dist[v] = min(dist[v], dist[u] + w) is a DP recurrence. Bellman–Ford is the pure DP version: when each round reads a copy of the previous round (as Cheapest Flights does), dist after k rounds = best path with ≤ k edges.

Do I need a visited[] array with Dijkstra?

Not with lazy deletion — the stale check d > dist[u] does the same job. Some people add visited[] and skip polled nodes; both are correct. Pick one and be consistent.

What is A*, and will they ask me for it?

A* is Dijkstra with a hint. The heap is ordered by dist[u] + h(u), where h never over-estimates the distance left (on a game map: the straight-line distance to the goal). It explores fewer nodes when the hint is good, and with h = 0 it is exactly Dijkstra. Interviews rarely need it beyond this explanation — Dijkstra is the must-know.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #743
    Network Delay Timemust-do
    MediumNetflixGoogleAmazon
  2. #787
    Cheapest Flights Within K Stopsmust-do
    MediumAirbnbFlipkartAmazonGoogleMeta
  3. #1514
    Path with Maximum Probability
    MediumGoogle
  4. #1631
    Path With Minimum Effortmust-do
    MediumGoogle
  5. #778
    Swim in Rising Water
    HardMetaGoogleAmazon
  6. #1334
    Find the City With the Smallest Number of Neighbors at a Threshold Distancemust-do
    MediumAmazon
  7. #1368
    Minimum Cost to Make at Least One Valid Path in a Grid
    HardGoogle
  8. #2290
    Minimum Obstacle Removal to Reach Cornermust-do
    HardGoogle
  9. #1976
    Number of Ways to Arrive at Destination
    MediumGoogleMeta

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #1091
    Shortest Path in Binary Matrix
    Mediumin Graphs

    The warm-up: every move costs the same, so plain BFS already is a shortest-path algorithm.

11 · revise

The whole chapter on one screen

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.

  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.

  3. template

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

  4. 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.

  5. trap

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

  6. trap

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

  7. trap

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

  8. pro tip

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

  9. pro tip

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

12 · recall

Flip, remember, repeat

card 1 / 13
recall

What does "relaxing" edge u → v mean?

tap or Space to flip ↻

Question 1: What does "relaxing" edge u → v mean?

13 · check yourself

Quick quiz

  1. 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?

  2. Why does Dijkstra require non-negative weights?

  3. You poll {7, node 3} but dist[3] is already 5. What do you do?

  4. In Floyd–Warshall, which loop must be outermost?

  5. After V − 1 rounds of Bellman–Ford, one more round still lowers a distance. What does it mean?

  6. Edge weights are only 0 or 1. What's the cleanest O(V + E) method?

  7. Cheapest Flights Within K Stops: why copy the cost array each Bellman–Ford round?

0/0 correct · 7 left

14 · learn more

A second teacher, if you want one