Shortest Paths: Dijkstra, Bellman-Ford, and Floyd-Warshall

BFS finds the shortest path in an unweighted graph because every edge costs the same, so the first arrival is always the shortest. The moment edges carry different weights, that guarantee breaks — a path through more edges can still be cheaper than a path through fewer, heavier ones. This lesson covers the three workhorse algorithms for weighted shortest paths, each suited to a different shape of problem.

What you’ll learn

• Dijkstra’s algorithm: a greedy, heap-driven search for single-source shortest paths when every weight is non-negative.
• Bellman-Ford: slower but strictly more general — handles negative edge weights and can detect a negative cycle.
• Floyd-Warshall: a dynamic-programming sweep that computes shortest paths between every pair of nodes at once.
• Which one to reach for, based on graph size, edge weights, and whether you need one source or every pair.

The cue

You are looking at a weighted shortest path when…

• You need a minimum cost, time, distance, price or risk to get somewhere, and the moves do not all cost the same. Equal costs mean BFS — do not pay for a heap you do not need.
• The input has explicit weights: [[u, v, w]], travel times, prices, probabilities, signal delays.
• The question is “minimum over all paths” of something that accumulates along the path. If instead it is a max-of-min (widest path) or a min-of-max (minimum bottleneck), the same heap works with the relaxation rule swapped.

Which of the three:

• one source, non-negative weights → Dijkstra, $O(E \log V)$.
• any negative weight, or “at most k edges” → Bellman-Ford, $O(V \cdot E)$.
• all pairs, small $V$ (roughly $\le 400$) → Floyd-Warshall, $O(V^3)$.

Reach for something else when every weight is equal (BFS), when the weights are only 0 and 1 (deque, $O(V+E)$), when you want to connect everything as cheaply as possible rather than travel (MST — a common and expensive confusion), or when the graph is a DAG (relax in topological order, $O(V+E)$, and negative weights are fine).

Visual intuition

The heap, not the graph, is where Dijkstra’s logic lives. Watch two things: the pop order (always the globally closest unfinalised node) and the stale entries that get skipped.

graphDijkstra: B is improved from 4 to 3 before it is ever settledO(E log V) with a binary heap

heap

A:0

1import heapq2 3def dijkstra(graph, start):4    dist = {v: inf for v in graph}5    dist[start] = 06    pq = [(0, start)]7    while pq:8        d, v = heapq.heappop(pq)9        if d > dist[v]: continue      # stale entry — skip10        for u, wt in graph[v]:11            nd = d + wt12            if nd < dist[u]:13                dist[u] = nd14                heapq.heappush(pq, (nd, u))15    return dist

seedEvery distance starts at infinity except A, which is 0. Dijkstra's promise: whichever unsettled node has the smallest tentative distance already has its *final* distance — provided no edge weight is negative.

Play‹›1/9⟲

The direct edge A→B costs 4, but A→C→B costs 1 + 2 = 3. Because the heap always pops the closest unfinalised node, C is settled first and B's distance drops to 3 before B is popped -- so the old (4, B) entry is still in the heap and gets skipped as stale. That skip is not a bug; it is what replaces a decrease-key operation.

Dijkstra’s algorithm: greedy + a min-heap

Dijkstra keeps a min-heap of (distance, node) pairs and always expands the closest unfinalized node next. Once a node is popped from the heap with its true shortest distance, that distance can never improve — which is exactly why negative weights break it: a “closest” node popped early could later be beaten by a path through a negative edge that hasn’t been discovered yet.

dijkstra.py

import heapq
from collections import defaultdict
 
 
def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))   # remove this line for a DIRECTED graph
 
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]          # (distance so far, node)
 
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue              # a shorter distance was already found -- stale entry
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist          # relax the edge
                heapq.heappush(heap, (new_dist, neighbor))
 
    return dist
 
 
n = 5
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print("shortest distances from 0:", dijkstra(n, edges, 0))

diagram Weighted graph -- Dijkstra relaxes the cheap 0-2-1 path before 0-1 mermaid

  graph LR
    N0((0)) -- "4" --> N1((1))
    N0 -- "1" --> N2((2))
    N2 -- "2" --> N1
    N1 -- "1" --> N3((3))
    N2 -- "5" --> N3
    N3 -- "3" --> N4((4))

Even though the direct edge 0 -> 1 costs 4, Dijkstra finds that 0 -> 2 -> 1 only costs 1 + 2 = 3 — cheaper. Because the heap always pops the globally closest unfinalized node next, this relaxation happens before node 1 is ever finalized at the (wrong) distance 4.

Stale heap entries are expected, not a bug

heapq has no “decrease-key” operation, so pushing a smaller distance for a node that’s already in the heap just adds a second, better entry instead of updating the first. The if d > dist[node]: continue check skips these stale leftovers cheaply — it’s the standard way to implement Dijkstra with Python’s heapq.

Bellman-Ford: handles negative weights, detects negative cycles

Instead of being greedy, Bellman-Ford brute-forces it: relax every edge, V - 1 times. After V - 1 rounds, every shortest path (which can use at most V - 1 edges in a graph with no negative cycle) is guaranteed correct. One extra round that still finds an improvement means a negative cycle exists — distances would keep shrinking forever.

bellman_ford.py

def bellman_ford(n, edges, source):
    dist = [float("inf")] * n
    dist[source] = 0
 
    for _ in range(n - 1):               # V-1 rounds is enough for any negative-cycle-free graph
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # One more round: any further improvement means a negative cycle exists.
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            return None, True             # (distances, has_negative_cycle)
 
    return dist, False
 
 
n = 5
# Directed, weighted edges -- Bellman-Ford handles negative weights directly.
edges = [(0, 1, 4), (0, 2, 1), (2, 1, -3), (1, 3, 2), (2, 3, 5), (3, 4, 1)]
distances, has_cycle = bellman_ford(n, edges, 0)
print("negative cycle?", has_cycle)
print("shortest distances from 0:", distances)

Why V - 1 rounds is exactly enough

A shortest path with no repeated node visits at most V - 1 edges (a path through all V nodes has V - 1 edges). Each full round of relaxation extends the guaranteed-correct portion of every shortest path by one edge, so after V - 1 rounds, every shortest path — however many edges it uses — has been fully relaxed.

Floyd-Warshall: all-pairs shortest paths

When you need the shortest distance between every pair of nodes at once (not just from one source), Floyd-Warshall’s triple-nested loop dynamic program does it directly. The recurrence considers, for each pair (i, j), whether routing through an intermediate node k shortens the known path:

$$dist[i][j] = \min\bigl(dist[i][j],\ dist[i][k] + dist[k][j]\bigr)$$

floyd_warshall.py

def floyd_warshall(n, edges):
    INF = float("inf")
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
 
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # keep the cheaper edge if there are duplicates
 
    for k in range(n):                    # k = the intermediate node allowed in this pass
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    return dist
 
 
n = 4
edges = [(0, 1, 3), (0, 3, 7), (1, 2, 1), (2, 3, 2)]
all_pairs = floyd_warshall(n, edges)
for row in all_pairs:
    print(row)
print("shortest 0 -> 3 via node 2:", all_pairs[0][3])   # 3 + 1 + 2 = 6, beats the direct 7

Loop order matters: k must be outermost

k (the intermediate node) has to be the outermost loop. By the time the i, j loops run for a given k, dist[i][k] and dist[k][j] must already reflect every intermediate node considered so far — swapping the loop order silently produces wrong answers for some pairs.

Complexity

Algorithm	Time	Space	Where the bound comes from
Dijkstra, binary heap	$O(E \log V)$	$O(V + E)$	each edge can push one heap entry, so the heap holds $O(E)$ items and $\log E = O(\log V)$
Dijkstra, Fibonacci heap	$O(E + V \log V)$	$O(V)$	real decrease-key; theoretically better, never worth writing in an interview
Dijkstra, dense array scan	$O(V^2)$	$O(V)$	scan for the minimum instead of a heap — better when $E \approx V^2$
Bellman-Ford	$O(V \cdot E)$	$O(V)$	$V-1$ rounds, every edge relaxed per round
Bellman-Ford, early exit	$O(k \cdot E)$	$O(V)$	stop when a round changes nothing; $k$ is the longest shortest-path in edges
Floyd-Warshall	$O(V^3)$	$O(V^2)$	three nested loops over all nodes; the matrix is the output
BFS (equal weights)	$O(V + E)$	$O(V)$	no ordering structure needed at all
0-1 BFS (deque)	$O(V + E)$	$O(V)$	only two distances ever in flight
DAG, topological relaxation	$O(V + E)$	$O(V)$	each node is final before it is used

Two practical notes worth saying out loud:

• $V-1$ rounds is not arbitrary. A shortest path visits at most $V$ nodes, so it has at most $V-1$ edges, and round $i$ guarantees every shortest path of $i$ edges is correct. That is also why an extra round detecting further improvement proves a negative cycle.
• Floyd-Warshall’s $O(V^3)$ is fine up to roughly $V \le 400$ ($6 \times 10^7$ operations). Above that, run Dijkstra from each source you actually need — and if you need all $10^{10}$ pairs of a $10^5$-node graph, the output is the problem, not the algorithm.

Which one to use

Algorithm	Handles negative weights?	Detects negative cycles?	Complexity	Best for
Dijkstra	No	No	$O((V + E) \log V)$	Single source, non-negative weights, large sparse graphs
Bellman-Ford	Yes	Yes	$O(V \cdot E)$	Single source, possible negative edges, or you must detect a negative cycle
Floyd-Warshall	Yes	Yes (diagonal goes negative)	$O(V^3)$	All-pairs shortest paths, small/dense graphs (roughly $V \lesssim 400$)

Default to Dijkstra, upgrade only when you must

If every edge weight is guaranteed non-negative, Dijkstra is almost always the right first instinct — it’s the fastest of the three. Reach for Bellman-Ford the moment negative weights are possible (currency arbitrage, “discount” edges), and Floyd-Warshall the moment the problem asks for distances between every pair, not just from one source.

Dry run

Dijkstra on the undirected graph from the template — edges = [(0,1,4), (0,2,1), (2,1,2), (1,3,1), (2,3,5), (3,4,3)], source 0.

pop	stale?	settle at	relaxations	dist	heap after
(0, 0)	no	0	1→4, 2→1	[0, 4, 1, ∞, ∞]	(1,2) (4,1)
(1, 2)	no	1	1→3 improved from 4, 3→6	[0, 3, 1, 6, ∞]	(3,1) (4,1) (6,3)
(3, 1)	no	3	3→4 improved from 6	[0, 3, 1, 4, ∞]	(4,1) (4,3) (6,3)
(4, 1)	yes — dist[1] is 3	—	skipped	unchanged	(4,3) (6,3)
(4, 3)	no	4	4→7	[0, 3, 1, 4, 7]	(6,3) (7,4)
(6, 3)	yes — dist[3] is 4	—	skipped	unchanged	(7,4)
(7, 4)	no	7	none	[0, 3, 1, 4, 7]	empty

Final: [0, 3, 1, 4, 7].

Four things this makes concrete:

• Node 1 is improved twice — 4, then 3 — and settled once. The direct edge costs 4, but the route through node 2 costs 3. The heap’s ordering guarantees node 2 (distance 1) is popped before node 1 (distance 4), so the improvement lands before node 1 is ever finalised. That ordering is Dijkstra’s correctness argument.
• Two of the seven pops are stale, and skipping them is the design, not a repair. heapq has no decrease-key, so an improvement pushes a second, better entry; the if d > dist[node]: continue guard discards the worse one when it surfaces. The heap therefore holds up to $O(E)$ entries, which is where the $\log E = O(\log V)$ factor comes from.
• A node is final the moment it is popped non-stale. Node 2 is settled at 1 and never reconsidered — nothing can beat it, because every remaining route starts from something already at distance ≥ 1 and adds a non-negative weight.
• That is exactly what a negative edge breaks. Add an edge 4 → 1 of weight -9 and node 1’s true distance becomes 7 - 9 = -2, but node 1 was finalised at 3 long before node 4 was reached. Dijkstra does not detect this — it returns a confidently wrong answer, which is why the negative-weight rule is a hard precondition rather than a performance note. Bellman-Ford’s $V-1$ rounds exist precisely to keep re-relaxing.

The variant map

Variant	What changes	Canonical problem
Plain single-source distances	the base template	LC 743 Network Delay Time
All weights equal	drop the heap — BFS is $O(V+E)$	LC 1091
Weights are 0 and 1	heap → deque, appendleft for 0	0-1 BFS · LC 1368
At most k edges	Bellman-Ford with exactly k+1 rounds — the round count is the edge budget, which a heap cannot express	LC 787 Cheapest Flights
Maximise a product of probabilities	push -prob, multiply instead of add; the “shortest” becomes the most probable	LC 1514
Minimise the maximum edge (bottleneck)	relax with max(d, w) instead of d + w	LC 1631 Path With Minimum Effort
Extra state per node	the heap key becomes a tuple, e.g. (cost, node, fuel_left)	Dijkstra with extra state · LC 1928
Count the shortest paths	keep ways[v]; on an improvement copy, on a tie add	LC 1976
Reconstruct the path	store parent[v] whenever you relax, then walk back	LC 1976
Negative cycle detection	one extra Bellman-Ford round: any further improvement means a negative cycle	arbitrage problems
All pairs, dense small graph	Floyd-Warshall, k as the outermost loop	LC 1334
DAG, any weights	relax in topological order, $O(V+E)$ — negatives are fine	LC 1857

Interview follow-ups

They ask	What they’re checking	The answer
“Why does Dijkstra fail on negative weights?”	The central precondition	Because it finalises a node the moment it is popped, on the assumption that no later route can be cheaper — which requires non-negative weights. A negative edge discovered afterwards would beat a finalised distance, and nothing goes back to fix it
“What are those stale heap entries?”	Whether you understand the implementation	heapq has no decrease-key, so improving a distance pushes a second, better entry. The if d > dist[node]: continue guard drops the obsolete one. The heap can hold $O(E)$ entries, hence $O(E \log V)$
“Why is the k in Floyd-Warshall the outermost loop?”	Whether you know why it works	Because k is the inductive parameter: after iteration k, dist[i][j] is the best path using only intermediates from $\{0..k\}$. Putting k inside is a genuinely wrong algorithm that happens to be right on many test cases
“At most k stops” (LC 787)	Recognising the shape	Bellman-Ford with k+1 rounds, relaxing from a snapshot of the previous round. The round count is the edge budget; a heap has no equivalent knob, and running Dijkstra with a hop count in the state also works but is easier to get wrong
“Detect currency arbitrage”	Applying the extra round	Bellman-Ford, then one more round: if anything still improves, a negative cycle is reachable. With logs and negated weights, a negative cycle is an arbitrage loop
“Return the path, not the distance”	Bookkeeping	Store parent[v] = u at relaxation time and walk back from the target. Recording parents on a rejected relaxation gives a path that is not shortest
“Minimise the largest single edge on the route”	Whether the pattern generalises	Same heap, different relaxation: new = max(d, w). Widest-path is min instead. The heap only needs the key to be monotone along a path, not additive
”$V = 10^5$, all-pairs distances?”	Scale sense	Impossible — the output alone is $10^{10}$ numbers. Ask what is actually needed: one source, or a small set of sources, run Dijkstra per source

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 743 — Network Delay Time · Medium

Problem. Given directed weighted edges times[i] = [u, v, w], n nodes and a source k, return the time for a signal from k to reach all nodes, or -1 if some node is unreachable.

Constraints. 1 <= k <= n <= 100, 1 <= len(times) <= 6000, 0 <= w <= 100.

Examples. times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 gives 2 · times = [[1,2,1]], n = 2, k = 2 gives -1

pch.exerciseTag pch.exerciseTitle

Editorial

Dijkstra’s invariant: because all weights are non-negative, the first time a node is popped from a min-heap its distance is final — nothing still in the heap could reach it more cheaply.

Time $O(E \log V)$. Space $O(V + E)$.

The if node in dist: continue line is doing real work. A node can be pushed several times with different tentative distances; this check discards the stale ones and replaces a separate visited set. Omitting it does not give wrong answers — the first pop already set the correct distance — but it re-expands neighbours needlessly.

The -1 case is reachability: len(dist) < n means the signal never arrived somewhere. ([[1,2,1]], 2, 2) starts at node 2, which has no outgoing edges, so node 1 is unreachable.

Note this requires non-negative weights. With a negative edge the first-pop invariant fails, and you need Bellman-Ford — which is the next problem’s territory.

Follow-ups: “Negative weights?” — Bellman-Ford, $O(VE)$, and it also detects negative cycles. “All-pairs shortest paths?” — Floyd-Warshall at $O(V^3)$, fine for n = 100. “Why does the first pop finalise a node?” — the non-negativity argument; be ready to state it. “Return the paths?” — store a predecessor per node.

LC 787 — Cheapest Flights Within K Stops · Medium

Problem. Given flights [from, to, price], find the cheapest price from src to dst using at most k stops. Return -1 if there is no such route.

Constraints. 1 <= n <= 100, 0 <= len(flights) <= n * (n - 1) / 2, 0 <= k < n.

Examples. n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 gives 700 · n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 gives 200, and with k = 0 gives 500

pch.exerciseTag pch.exerciseTitle

Editorial

The hop limit is what makes Dijkstra a poor fit: it finalises nodes by cost, but the cheapest way to reach a node may use too many stops to be extendable. Bellman-Ford is naturally suited, because its rounds correspond exactly to edge counts.

Time $O(k \times E)$. Space $O(n)$.

The snapshot is essential

nxt = dist[:] and relaxing from dist into nxt guarantees round i uses paths of at most i edges. Relaxing in place would let one round chain several edges: u gets updated, then an edge out of u is relaxed using that brand-new value, quietly using two edges in one round and breaking the hop limit.

The first test case is exactly this trap. With k = 1 the answer is 700 (0 -> 1 -> 3); the cheaper 0 -> 1 -> 2 -> 3 costs 400 but uses two stops. An in-place relaxation finds 400 and is wrong.

The third case, k = 0, allows a single edge — so the direct 0 -> 2 flight at 500 beats the two-hop 200.

Dijkstra can be adapted by carrying (cost, node, stops) in the heap and allowing a node to be revisited with fewer stops, but the state space grows and the bookkeeping is easier to get wrong.

Follow-ups: “Why not plain Dijkstra?” — the finalisation argument above; the most likely question. “Detect negative cycles?” — run one extra round; any further improvement proves a negative cycle. “Exactly k stops?” — read the answer from round k + 1 only. “Very large k?” — once k >= n - 1 the limit is irrelevant and plain Dijkstra applies.

LC 1631 — Path With Minimum Effort · Medium

Problem. Given a grid of heights, a route’s effort is the maximum absolute height difference between consecutive cells on it. Return the minimum effort to travel from the top-left to the bottom-right, moving in 4 directions.

Constraints. 1 <= rows, cols <= 100, 1 <= heights[i][j] <= 10^6.

Examples. [[1,2,2],[3,8,2],[5,3,5]] gives 2 · [[1,2,3],[3,8,4],[5,3,5]] gives 1 · a grid with a zero-difference route gives 0

pch.exerciseTag pch.exerciseTitle

Editorial

Dijkstra is usually taught with additive costs, but it works for any path cost that is monotone non-decreasing as the path extends. max() qualifies: adding a step can only keep the effort the same or raise it, never lower it. So the first-pop-is-final invariant still holds.

Time $O(rc \log(rc))$. Space $O(rc)$.

The only change from a standard Dijkstra is the relaxation:

python

ne = max(e, abs(height_difference))     # instead of e + weight

That generalisation — “Dijkstra needs monotonicity, not addition” — is the transferable insight, and it also covers minimax and bottleneck path problems generally.

Two alternatives worth naming:

• Binary search + BFS. Guess a threshold effort, then check with BFS/DFS whether the destination is reachable using only steps within it. That is binary search on the answer at $O(rc \log(\max h))$, and many find it easier to reason about.
• Union-find. Sort all edges by difference and union them in order until the corners connect; the last edge’s difference is the answer — essentially building a minimum spanning tree, which is Kruskal’s.

[[3]] gives 0 — a single cell needs no moves.

Follow-ups: “Why does Dijkstra still work?” — the monotonicity argument; the expected question. “Do it with binary search?” — the alternative above. “With union-find?” — the Kruskal framing. “8 directions?” — extend the offsets; nothing else changes.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

5 problems

0 easy4 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○743Network Delay TimemediumDijkstra straight from the template above: how long until a signal reaches every node from one sourceNeetCode 150googleuberamazon
• ○787Cheapest Flights Within K StopsmediumA Bellman-Ford variant capped at `K + 1` relaxation rounds instead of `V - 1`NeetCode 150googleuberamazon
• ○1334Find the City With the Smallest Number of Neighbors at a Threshold DistancemediumFloyd-Warshall's all-pairs table, then count reachable cities per city
• ○1631Path With Minimum EffortmediumDijkstra where the "distance" being minimized is the maximum edge weight along the path, not the sum
• ○778Swim in Rising WaterhardDijkstra-style: a min-heap greedily expanding to the lowest-elevation unvisited cell, minimizing the *maximum* value on the pathNeetCode 150

Self-check

pch.quizTag Weighted shortest paths — self-check

1. Why does a single negative edge break Dijkstra?

   A The heap cannot store negative numbers B Because Dijkstra finalises a node the moment it is popped, assuming no later route can be cheaper — a negative edge found afterwards would beat that finalised distance, and nothing revisits it C It causes an infinite loop D It does not; only negative cycles break it
   pch.quizShowAnswer

   B — Because Dijkstra finalises a node the moment it is popped, assuming no later route can be cheaper — a negative edge found afterwards would beat that finalised distance, and nothing revisits it — Note the failure mode: no crash, no loop — a confidently wrong answer. That is why non-negative weights are a precondition rather than a performance note, and why Bellman-Ford's repeated rounds exist.

2. Your heap pops (4, node 1) but dist[1] is already 3. What is going on?

   A A bug in the relaxation B A stale entry: heapq has no decrease-key, so improving a distance pushes a second, better entry — the `if d > dist[node]: continue` guard discards the obsolete one C Node 1 is unreachable D The graph has a negative edge
   pch.quizShowAnswer

   B — A stale entry: heapq has no decrease-key, so improving a distance pushes a second, better entry — the `if d > dist[node]: continue` guard discards the obsolete one — Both stale pops in the dry run are expected. It also explains the complexity: the heap holds O(E) entries rather than O(V), giving O(E log V).

3. In Floyd-Warshall, why must `k` be the outermost loop?

   A For cache efficiency B Because k is the inductive parameter: after iteration k, dist[i][j] is the best path using only intermediates from {0..k}. Moving k inside is a different, wrong algorithm C Because i and j must be sorted D The order does not matter
   pch.quizShowAnswer

   B — Because k is the inductive parameter: after iteration k, dist[i][j] is the best path using only intermediates from {0..k}. Moving k inside is a different, wrong algorithm — The wrong loop order is dangerous precisely because it passes many test cases. If you can state the invariant, you can also derive the loop order rather than memorising it.

4. LC 787: cheapest flight with at most k stops. Why Bellman-Ford rather than Dijkstra?

   A Because the weights may be negative B Because the round count IS the edge budget — k+1 rounds, relaxing from a snapshot of the previous round — and a heap has no equivalent knob C Because Dijkstra is too slow here D Because the graph is undirected
   pch.quizShowAnswer

   B — Because the round count IS the edge budget — k+1 rounds, relaxing from a snapshot of the previous round — and a heap has no equivalent knob — Dijkstra with a hop count folded into the state also works, but it is easier to get wrong: the cheapest route to a node is not necessarily the one leaving the most hops available.

5. The problem asks to minimise the LARGEST single edge on the route, not the total. What changes?

   A Nothing works; this needs a different algorithm B The same heap with a different relaxation: `new = max(d, w)` instead of `d + w` — the key only has to be monotone along a path, not additive C Sort the edges and binary search only D Use Floyd-Warshall
   pch.quizShowAnswer

   B — The same heap with a different relaxation: `new = max(d, w)` instead of `d + w` — the key only has to be monotone along a path, not additive — Widest path swaps in `min` the same way. Recognising that Dijkstra needs monotonicity rather than addition is what lets you reuse it for bottleneck, probability (LC 1514) and reliability problems.

6. Every edge weight is 1. What should you use?

   A Dijkstra — it handles that case too B BFS: O(V + E) with no ordering structure. Dijkstra is correct but pays a log factor for sorting that a queue gives free C Floyd-Warshall D Bellman-Ford
   pch.quizShowAnswer

   B — BFS: O(V + E) with no ordering structure. Dijkstra is correct but pays a log factor for sorting that a queue gives free — Reaching for the heavier tool when the weights are uniform is a common tell in interviews. The same reasoning one step up: weights of only 0 and 1 want a deque, not a heap.

Recall card

• Cue — minimum cost/time/distance where moves cost different amounts. Equal costs → BFS; 0/1 → deque.
• Dijkstra — heap of (dist, node); pop, skip if d > dist[node] (stale), relax neighbours, push improvements. $O(E \log V)$. Non-negative weights only.
• A popped non-stale node is final — that is the whole correctness argument, and exactly what a negative edge invalidates.
• Bellman-Ford — $V-1$ rounds over all edges, $O(V\cdot E)$. Handles negatives; one extra round detects a negative cycle; k+1 rounds answers “at most k edges”.
• Floyd-Warshall — k outermost, then i, j; $O(V^3)$, good to about $V \le 400$; a negative value on the diagonal means a negative cycle.
• DAG — relax in topological order: $O(V+E)$ and negatives are fine.
• Same heap, different relaxation — max(d, w) for bottleneck, min for widest, multiply for probabilities.
• Path — store parent[v] when you relax, then walk back.

Recap

• Dijkstra: greedy + min-heap, $O((V + E) \log V)$, but only correct when every weight is non-negative.
• Bellman-Ford: relax every edge $V - 1$ times, $O(V \cdot E)$; a V-th round that still improves something means a negative cycle.
• Floyd-Warshall: triple loop with k outermost, $O(V^3)$, computes every pair’s shortest distance in one pass.
• Default to Dijkstra; drop to Bellman-Ford for negative edges or cycle detection; reach for Floyd-Warshall only when you need all-pairs distances on a graph small enough for $O(V^3)$.

With traversal, components, and weighted shortest paths covered, you have the core toolkit for nearly every graph question that shows up in interviews and competitive programming alike.