THE SAME GRAPH, EVERY ALGORITHM
Five algorithms that are one idea under different amounts of pressure: relax an edge, keep the best distance so far. What changes is only when you are allowed to call a distance final.
This is not a list of problems. It is 15 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
13 PROBLEMS · 6 LINK TO LEETCODE · THE REST ARE CONCEPTS THE DRILLS COVER
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here.
Every algorithm in this deck is the same idea — relax an edge, keep the best distance. What changes is when you may call a distance final, and the statement tells you which rule you are allowed.
Unweighted, or the statement says each move costs the same.
Plain BFSO(V + E)A DAG — and negative weights are still fine here.
Topological order, then relaxO(V + E)One source, and you need distances to everything.
Dijkstra with a heapO(E log V)Or you are asked to detect a negative cycle at all.
Bellman-FordO(V · E)n ≤ a few hundred, or the graph is dense.
Floyd-WarshallO(V³)At most k stops, at most k moves — cost alone is not enough state.
Sweep by level, not by costO(k · E)When every edge costs the same, the first time BFS reaches a node is already the cheapest way to reach it. No priority queue, no revisiting, no relaxation — a plain FIFO queue is the whole algorithm. This unit is the baseline the rest of the deck is measured against.
WHY IS PLAIN BFS ENOUGH WHEN EVERY EDGE COSTS THE SAME?
In unit-weight BFS, at what moment is a node's distance final?
The queue holds nodes in non-decreasing distance order, so the first path to reach a node is via the shallowest frontier that could reach it. Nothing later can be shorter. That is why the code writes dist[v] at push time and never touches it again — and it is exactly the guarantee weights destroy.
On the deck's graph with every edge costing 1, what is dist[6] from node 1?
1 → 2 → 3 → 6 and 1 → 4 → 5 → 6 both take three hops, and nothing reaches 6 in two. Step the visualiser on the previous slide and watch 6 turn gold on the third wave.
A student marks nodes visited when they POP instead of when they PUSH. What actually goes wrong?
The distances stay correct, which is what makes this bug so hard to catch. But a node can be enqueued once per incoming edge before its first pop, so the queue grows toward O(E) copies and the runtime degrades badly on dense graphs. Mark on push.
Watch the distance row. Every cell is written exactly once and never revised — that is what makes this correct, and it is precisely the property Dijkstra has to work to recover.
The statement says shortest path, and every edge is either unweighted or explicitly costs the same. That single sentence is worth an entire priority queue — reach for a plain queue and stop.
BFS explores in waves: everything one hop away, then everything two hops away. Because each wave costs exactly one more than the last, the wave a node first appears in is its shortest distance. No later wave can do better, so the value is final the instant it is written.
vector<int> shortestPath(int V, vector<vector<int>>& adj, int src) { vector<int> dist(V, -1); // -1 doubles as the visited mark queue<int> q; dist[src] = 0; q.push(src); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { // first sight is already final dist[v] = dist[u] + 1; q.push(v); // mark on PUSH, not on pop } } } return dist; }
from collections import deque def shortest_path(V, adj, src): dist = [-1] * V # -1 doubles as the visited mark dist[src] = 0 q = deque([src]) while q: u = q.popleft() for v in adj[u]: if dist[v] == -1: # first sight is already final dist[v] = dist[u] + 1 q.append(v) # mark on PUSH, not on pop return dist
Do not initialise dist[] to 0. Zero is a legitimate distance (the source), so it is useless as an unvisited marker — you will silently treat every node as already reached and return all zeros. Use −1 or a large sentinel.
A DAG has no cycles, so its nodes can be laid in a line where every edge points forward. Process them in that order and by the time you reach a node, every path into it has already been considered. One pass, no queue, and negative weights are perfectly safe.
WHY DOES TOPOLOGICAL ORDER MAKE A SINGLE PASS ENOUGH?
Why is one pass in topological order enough to finalise every distance?
Topological order guarantees every edge points forward. So when you arrive at node v, every u with an edge u → v sits earlier in the order and has already been finalised. There is no later discovery that could improve v — the order does the work a priority queue would otherwise have to do.
This graph is a DAG and some edges have negative weights. Which algorithm is correct AND cheapest?
Bellman-Ford is correct but costs O(V · E) for no reason. Dijkstra is genuinely wrong — its settle rule assumes extending a path never makes it cheaper, and a negative edge breaks that on a DAG too. Topological order needs no such assumption, so it stays correct at O(V + E).
Someone starts relaxing edges while the topological sort is still running. What breaks?
The entire correctness argument is predecessors first. Relax v before some u → v has settled and you may commit a value no later step ever revisits, because a single pass never comes back. Finish the sort, then relax in that order.
Directed, guaranteed acyclic, and asking for shortest paths — often with weights that may be negative. The word acyclic is the whole signal: it buys you an order in which one pass suffices.
Lay the nodes out so every edge points forward. Now sweep left to right: when you arrive at a node, every path into it has already been finalised, so its distance cannot improve later. The topological order replaces the priority queue — and unlike Dijkstra, it never assumes weights are non-negative.
// assumes topo[] holds a valid topological order of the DAG vector<int> shortestPathDAG(int V, vector<vector<pair<int,int>>>& adj, vector<int>& topo, int src) { const int INF = 1e9; vector<int> dist(V, INF); dist[src] = 0; for (int u : topo) { if (dist[u] == INF) continue; // unreachable — never relax from it for (auto [v, w] : adj[u]) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w; // negative w is fine on a DAG } return dist; }
INF = float('inf')
def shortest_path_dag(V, adj, topo, src):
dist = [INF] * V
dist[src] = 0
for u in topo:
if dist[u] == INF: # unreachable - never relax from it
continue
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w # negative w is fine on a DAG
return distSkipping the ∞ check relaxes from unreachable nodes: ∞ + w overflows to a large negative in fixed-width ints, and suddenly unreachable nodes have finite distances. Guard with if (dist[u] != INF) before relaxing anything.
Weights break the BFS guarantee: the first path to reach a node need not be the cheapest. Dijkstra's repair is a rule about when you may stop worrying — always finalise the smallest unsettled distance, because with non-negative weights nothing still pending can undercut it.
WHEN IS IT SAFE TO CALL A DISTANCE FINAL, ONCE EDGES HAVE COSTS?
Why is it safe to finalise the smallest unsettled distance?
Any other route to that node must leave through some node still in the queue, which already costs at least as much — and every further edge adds a non-negative amount on top. So no pending path can come in cheaper. Notice this argument uses non-negativity twice; that is why one negative edge is enough to break it.
On the deck's weighted graph, starting from node 1, which node is settled SECOND?
Node 1 settles first at 0 and relaxes two edges: 1→2 costs 4 and 1→4 costs 2. Dijkstra takes the smallest, so node 4 settles at 2 — even though 2 and 4 were discovered in the same step. Step the mechanism slide and watch the priority queue reorder.
A student marks nodes visited on PUSH, exactly as they learned in BFS. What happens?
This is the single most common Dijkstra bug, and it comes from carrying the BFS habit across. On our graph node 8 is discovered at 13 and later improved to 10. Freeze it on push and you ship 13 and never notice. Mark settled on POP.
Watch node 8. It is discovered at 13 via node 5, then improved to 10 via node 7 — after it was already in the queue. Discovery is a guess; settling is the commitment.
Weighted edges, all non-negative, and a single source. That is Dijkstra's exact domain — and the moment you spot one negative weight, it is not, no matter how the problem is phrased.
Keep a best-known distance for every node and repeatedly commit to the smallest one still open. With non-negative weights, nothing left in the queue can reach it for less, so committing is safe. Discovery is a guess that can improve; settling is permanent.
vector<int> dijkstra(int V, vector<vector<pair<int,int>>>& adj, int src) { const int INF = 1e9; vector<int> dist(V, INF); priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // min-heap on distance dist[src] = 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // stale copy, already settled cheaper for (auto [v, w] : adj[u]) if (d + w < dist[v]) { dist[v] = d + w; // settle on POP, never on push pq.push({dist[v], v}); } } return dist; }
import heapq def dijkstra(V, adj, src): INF = float('inf') dist = [INF] * V dist[src] = 0 pq = [(0, src)] # min-heap on distance while pq: d, u = heapq.heappop(pq) if d > dist[u]: # stale copy, already settled cheaper continue for v, w in adj[u]: if d + w < dist[v]: dist[v] = d + w # settle on POP, never on push heapq.heappush(pq, (dist[v], v)) return dist
Never mark a node visited when you push it. On this deck's graph node 8 is discovered at 13 and later improved to 10 — freeze it on push and you return 13 with no error anywhere. Settle on POP, and skip stale entries with if (d > dist[u]) continue;
Same algorithm, different container. An ordered set keeps the smallest distance at its front and lets you erase the outdated entry — the one thing a binary heap cannot do. Fewer stale copies, at the price of a log-time erase.
WHY WOULD YOU REACH FOR A SET INSTEAD OF A PRIORITY QUEUE?
What does the set version give you that the priority-queue version cannot?
A binary heap has no way to find and remove an arbitrary element, so the PQ version leaves stale pairs behind and skips them on pop. A set can erase({old, v}) the moment a better distance is found, so it never holds more than one entry per node. Same complexity class, smaller structure.
Is the set version therefore faster than the priority-queue version?
Both are O(E log V). The set does fewer, more expensive operations; the heap does more, cheaper ones. In practice a heap often wins on constant factors, and it is what most people write. Choose the set when you genuinely need the erase, not because it sounds tighter.
A student updates <code>dist[v]</code> first, then calls <code>st.erase({dist[v], v})</code>. What happens?
The set is keyed on the pair. Overwrite dist[v] first and you are asking it to erase {new, v}, which is not in the set — the stale {old, v} survives. Erase with the old value, then assign. The result is still correct, just silently back to carrying stale entries.
This lecture is the one that looks skippable and is not. It answers why the container has to be ordered, and derives the O(E log V) you will be asked to justify out loud in an interview.
WHY A PRIORITY QUEUE, AND WHERE EXACTLY DOES O(E log V) COME FROM?
You swap the priority queue for a plain FIFO queue but keep the relaxation check. What happens?
It still terminates with correct distances — you have essentially written SPFA. What you lose is the settle-once guarantee: a node can be popped and re-expanded repeatedly as better distances arrive, and the work blows up toward O(V·E). The heap is about how much work, not whether the answer is right.
In O(E log V), where does the E come from?
Every push into the heap is caused by some edge succeeding at d + w < dist[v], so the heap receives at most E entries over the whole run. Each of those pushes and its matching pop costs log of the heap size, which is bounded by E — and since log E ≤ 2 log V, that is written log V.
Not a problem to solve — a claim to be able to defend. Any interview that accepts Dijkstra will ask you why the container is ordered and what the complexity is.
The priority queue is not what makes Dijkstra correct; the non-negative weights are. The heap is what makes it fast, by ensuring each node is expanded once instead of once per improvement.
// Why the ORDER matters, in one comparison: // // plain queue -> a node can be popped and re-expanded every time a // better distance arrives. Still correct. Work blows // up toward O(V * E). // // min-heap -> the smallest unsettled distance is final on pop, so // each node is expanded exactly once. // // Cost accounting for the heap version: // // pushes <= E (one per successful relaxation) // pops <= E // per op = log(heap size) <= log E <= 2 log V // ------------------------------------------------- // total = O(E log V)
# Why the ORDER matters, in one comparison: # # plain queue -> a node can be popped and re-expanded every time a # better distance arrives. Still correct. Work blows # up toward O(V * E). # # min-heap -> the smallest unsettled distance is final on pop, so # each node is expanded exactly once. # # Cost accounting for the heap version: # # pushes <= E (one per successful relaxation) # pops <= E # per op = log(heap size) <= log E <= 2 log V # ------------------------------------------------- # total = O(E log V)
Do not answer O(V log V)
by reflex. That is the bound for a Fibonacci heap, not the binary heap you actually wrote. With a standard priority queue it is O(E log V), and on a dense graph E dominates V badly.
Half of all shortest-path follow-ups are now print the route. It costs one extra array: whenever you improve a node, record who improved it. Walk that chain backwards from the target and reverse it.
HOW DO YOU RETURN THE PATH ITSELF, NOT JUST ITS LENGTH?
On the deck's weighted graph from node 1, what is parent[8] when Dijkstra finishes?
Node 5 did discover 8 first, at distance 13 — so parent[8] was briefly 5. Then node 7 settled at 9 and offered 9 + 1 = 10, which is better, so both dist[8] and parent[8] were overwritten. The parent is whoever last improved you, not whoever found you.
At which moment should parent[v] be written?
The parent must always agree with the distance it explains. Write it in the same if that assigns dist[v] and the two can never drift apart. Write it at settle time and you have lost which edge produced the winning value.
A student leaves <code>par[]</code> zero-initialised and walks back with <code>while (at != src)</code>. What can go wrong?
Zero is a valid node id, so an untouched entry is indistinguishable from a real parent of node 0. On an unreachable target the walk then steps into node 0 and can cycle there forever. Use iota(par.begin(), par.end(), 0) so every node starts as its own parent, and check dist[dst] != INF before walking at all.
Phase one is Dijkstra, now recording who improved whom. Phase two walks parent[] backwards from node 8. Note the answer is 1 → 4 → 7 → 8 and not via node 5 — node 8's parent was overwritten when the cheaper route arrived.
A grid is a graph you did not have to build: each cell is a node, each legal move is an edge. Because every move costs exactly one, this is unit-weight BFS from unit 1 — wearing a different costume.
WHEN IS A GRID SHORTEST-PATH JUST BFS, AND WHEN IS IT NOT?
Why is BFS sufficient here rather than Dijkstra?
The cell values mark blocked or free — they are not edge costs. Every move you are allowed to make costs one, so the unit-weight argument from unit 01 applies unchanged and a plain queue is enough. Dijkstra here is correct but a log factor slower for nothing.
Your GfG solution is accepted but the same code fails LeetCode 1091. What is the most likely cause?
This exact mismatch bites people who practise both. LC 1091 is 8-directional — diagonals are legal moves — so a 4-direction delta array returns a longer path or −1 on cases that clearly have an answer. Read the movement rules before reusing a grid template.
A student returns <code>dist[n-1][n-1]</code> having started with <code>dist[0][0] = 0</code>. The judge says every answer is one too small. Why?
LC 1091 asks for the length of the path in cells visited, not the number of moves. A single-cell grid whose only cell is free has answer 1, not 0. Start the source at 1 — an off-by-one that lives specifically in this family of problems.
A grid of blocked and free cells, and a question about the fewest steps. You are never handed an adjacency list — the grid is the graph, and every legal move costs one.
Treat each free cell as a node and each legal move as an edge of weight 1, then run the unit-weight BFS from unit 01 unchanged. The only real work is the bookkeeping: bounds, blocked cells, and how the answer is counted.
int shortestPathBinaryMatrix(vector<vector<int>>& grid) { int n = grid.size(); if (grid[0][0] || grid[n-1][n-1]) return -1; // blocked before we start vector<vector<int>> dist(n, vector<int>(n, -1)); queue<pair<int,int>> q; dist[0][0] = 1; // the problem counts CELLS, not moves q.push({0, 0}); int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1}; // all 8 — LC 1091 allows diagonals int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1}; while (!q.empty()) { auto [r, c] = q.front(); q.pop(); if (r == n-1 && c == n-1) return dist[r][c]; for (int k = 0; k < 8; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue; if (grid[nr][nc] || dist[nr][nc] != -1) continue; dist[nr][nc] = dist[r][c] + 1; q.push({nr, nc}); } } return -1; }
from collections import deque def shortestPathBinaryMatrix(grid): n = len(grid) if grid[0][0] or grid[n-1][n-1]: return -1 # blocked before we start dist = [[-1] * n for _ in range(n)] dist[0][0] = 1 # the problem counts CELLS, not moves q = deque([(0, 0)]) DIRS = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] # all 8 - LC 1091 allows diagonals while q: r, c = q.popleft() if r == n-1 and c == n-1: return dist[r][c] for dr, dc in DIRS: nr, nc = r + dr, c + dc if not (0 <= nr < n and 0 <= nc < n): continue if grid[nr][nc] or dist[nr][nc] != -1: continue dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc)) return -1
Two off-by-ones live here. The answer counts cells, so the source starts at 1 and a 1×1 free grid answers 1. And LC 1091 is 8-directional — a 4-direction delta array copied from a GfG solution silently returns longer paths.
The walkthrough for #05 Shortest Distance in a Binary Maze. Watch it, then go straight back and write it yourself.
The cost of a route here is not the sum of its steps — it is the single worst step on it. Dijkstra survives that change untouched, because the only thing it ever needed was that extending a path cannot make it cheaper.
WHAT IF A PATH'S COST IS ITS WORST EDGE, NOT ITS TOTAL?
What single line changes when you move from shortest-sum to minimum-effort?
Everything else is identical Dijkstra. You are still repeatedly settling the smallest unsettled label — the label just combines differently. Recognising that a whole family of problems is 'Dijkstra with a different combine' is worth far more than memorising this one.
Why is Dijkstra still correct once the combine is max instead of +?
Dijkstra's settle rule needs exactly one guarantee: nothing pending can come back cheaper. With sums that comes from non-negative weights; with max it comes from max(d, x) ≥ d. Same argument, different operator — which is why negative weights break sums but nothing breaks max.
A student accumulates <code>d + abs(diff)</code> and returns that. What do they get?
It is a perfectly good answer to a different question. Minimising total climb prefers many small steps; minimising the worst step will happily take a long flat detour to avoid one cliff. Both are shortest paths — read which cost function the statement is asking for.
A grid, and a cost defined as the maximum difference along the route rather than the total. Any phrasing like minimise the worst step, the bottleneck, or the largest jump is this problem.
Run Dijkstra where a node's label is the worst step needed to reach it. Relaxing an edge takes max(label so far, this step). Because max never decreases a label, the settle-the-smallest rule is as safe as it was with sums.
int minimumEffortPath(vector<vector<int>>& h) { int m = h.size(), n = h[0].size(); vector<vector<int>> eff(m, vector<int>(n, INT_MAX)); priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq; eff[0][0] = 0; pq.push({0, 0, 0}); int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; while (!pq.empty()) { auto [d, r, c] = pq.top(); pq.pop(); if (r == m-1 && c == n-1) return d; // settled: this is the answer if (d > eff[r][c]) continue; // stale copy for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue; int cand = max(d, abs(h[nr][nc] - h[r][c])); // MAX, not + if (cand < eff[nr][nc]) { eff[nr][nc] = cand; pq.push({cand, nr, nc}); } } } return 0; }
import heapq def minimumEffortPath(h): m, n = len(h), len(h[0]) eff = [[float('inf')] * n for _ in range(m)] eff[0][0] = 0 pq = [(0, 0, 0)] while pq: d, r, c = heapq.heappop(pq) if r == m-1 and c == n-1: return d # settled: this is the answer if d > eff[r][c]: continue # stale copy for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)): nr, nc = r + dr, c + dc if not (0 <= nr < m and 0 <= nc < n): continue cand = max(d, abs(h[nr][nc] - h[r][c])) # MAX, not + if cand < eff[nr][nc]: eff[nr][nc] = cand heapq.heappush(pq, (cand, nr, nc)) return 0
Summing the differences instead of taking their max answers a different question — least total climb, not least worst step. Both are legitimate shortest-path problems, and the judge only accepts one of them.
The walkthrough for #06 Path With Minimum Effort. Watch it, then go straight back and write it yourself.
The first problem in this deck where Dijkstra is the wrong tool. Adding a hop limit means a node is no longer described by one number, and the moment that happens, settling on cost alone throws away the answer.
WHY DOES DIJKSTRA FAIL THE INSTANT YOU ADD A STOP LIMIT?
Why can plain Dijkstra return a wrong answer here?
Dijkstra's whole premise is that once a node is settled you never revisit it. But cheap with 5 stops and expensive with 1 stop are both useful, and the limit decides which. The moment a second dimension constrains the answer, one number per node is not enough state.
Where does the k+1 in the loop bound come from?
A direct flight has zero stops and one edge. Allowing k stops therefore allows k+1 edges, so you relax the edge list k+1 times. Reading it as k passes is the single most common wrong submission on this problem.
Doing k+1 Bellman-Ford passes, a student relaxes into <code>dist[]</code> directly instead of a copy. What breaks?
Each pass must mean exactly one more edge. Writing into the live array lets a value updated earlier in the same sweep be extended again immediately, so one pass can advance several hops and the limit stops being enforced. Relax from a snapshot taken at the start of the pass.
A shortest-path question with a second budget attached — at most k stops, at most k moves, at most k refuels. The extra limit is the signal that cost alone is not enough state.
Because a city is only fully described by (city, stops used), settling on price is unsafe. Sweep by stops instead: relax the whole edge list once per allowed flight, k+1 times. Every value written after i sweeps uses at most i edges, so the limit enforces itself.
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { const int INF = 1e9; vector<int> dist(n, INF); dist[src] = 0; for (int pass = 0; pass <= k; pass++) { // k stops == k+1 flights vector<int> tmp = dist; // snapshot: one edge per pass for (auto& f : flights) { int u = f[0], v = f[1], w = f[2]; if (dist[u] != INF && dist[u] + w < tmp[v]) tmp[v] = dist[u] + w; // read dist, write tmp } dist = tmp; } return dist[dst] == INF ? -1 : dist[dst]; }
def findCheapestPrice(n, flights, src, dst, k): INF = float('inf') dist = [INF] * n dist[src] = 0 for _ in range(k + 1): # k stops == k+1 flights tmp = dist[:] # snapshot: one edge per pass for u, v, w in flights: if dist[u] != INF and dist[u] + w < tmp[v]: tmp[v] = dist[u] + w # read dist, write tmp dist = tmp return -1 if dist[dst] == INF else dist[dst]
Relax into the live array and one sweep can chain several flights together, quietly allowing more than k stops. Snapshot dist at the start of each pass and read from the snapshot — that is what makes a pass mean exactly one more edge.
The walkthrough for #07 Cheapest Flight Within K Stops. Watch it, then go straight back and write it yourself.
Plain Dijkstra, with the answer read off differently: you are not asked about one destination but about the last node to hear the signal — so the answer is the maximum over all shortest distances.
WHEN THE QUESTION IS ABOUT EVERYONE, WHAT DO YOU RETURN?
What exactly is the value you return?
The network is fully informed only once its slowest recipient has the signal, so you want the worst case among the best routes — a max over the dist array. Returning the last node popped is a tempting shortcut and is wrong whenever ties or unreachable nodes exist.
Your solution passes locally and fails on the judge with an off-by-one. Most likely cause?
LC 743 labels nodes 1 through n. Size dist as n and node n writes off the end; loop 0..n-1 and you check a node that does not exist while missing one that does. Size n+1 and iterate 1..n — the same indexing discipline unit 01 flagged.
One source, and a question about all nodes rather than one — how long until everyone has it, does everyone get it at all. Single Dijkstra, different read-out.
Run Dijkstra once from the source. Each node's shortest distance is when it hears the signal, so the network is fully informed at the maximum of those. If any node is still ∞, it never hears it and the answer is −1.
int networkDelayTime(vector<vector<int>>& times, int n, int k) { const int INF = 1e9; vector<vector<pair<int,int>>> adj(n + 1); // 1-indexed: size n+1 for (auto& t : times) adj[t[0]].push_back({t[1], t[2]}); vector<int> dist(n + 1, INF); priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; dist[k] = 0; pq.push({0, k}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : adj[u]) if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); } } int worst = 0; for (int i = 1; i <= n; i++) { // 1..n, not 0..n-1 if (dist[i] == INF) return -1; worst = max(worst, dist[i]); } return worst; }
import heapq from collections import defaultdict def networkDelayTime(times, n, k): adj = defaultdict(list) for u, v, w in times: adj[u].append((v, w)) INF = float('inf') dist = {i: INF for i in range(1, n + 1)} # 1-indexed dist[k] = 0 pq = [(0, k)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in adj[u]: if d + w < dist[v]: dist[v] = d + w heapq.heappush(pq, (dist[v], v)) worst = max(dist.values()) return -1 if worst == INF else worst
Do not return the distance of the last node popped. With ties, the final pop is not necessarily the maximum, and an unreachable node never pops at all — so that shortcut silently reports success on a disconnected network.
The walkthrough for #08 Network Delay Time. Watch it, then go straight back and write it yourself.
Two answers at once: the shortest distance, and how many distinct routes achieve it. The counting rides along with the relaxation, and it is correct only because Dijkstra settles each node exactly once.
HOW DO YOU COUNT SHORTEST PATHS WITHOUT ENUMERATING THEM?
When you relax u → v and find d + w == dist[v], what happens to ways[v]?
A tie means you have found another equally short way to reach v, and every shortest route into u extends into one for v. So the counts add. Only a strictly better distance discards the old count, because those routes are no longer shortest at all.
Why is it safe to add counts when u is popped, rather than at the very end?
This is the whole reason the trick works. When u comes off the heap its distance is final, and therefore so is its count of shortest routes — nothing later can add another. Do this on an algorithm that revisits nodes and you will double-count.
A student stores <code>ways[]</code> as <code>int</code> and applies the modulus only when returning. What goes wrong?
Path counts grow combinatorially and blow past 2³¹ on large graphs. Overflow in C++ is silent, so you get a plausible wrong number with no crash. Take the modulus at every addition, and keep the array in a 64-bit type while you are at it.
Shortest path, and then how many of them. Any statement asking for the number of ways, modulo 1e9+7, on top of a distance query is this pattern.
Carry a second array alongside the distances. When you find a strictly shorter route to v, its old count is obsolete — replace it. When you find an equally short one, every shortest route into u becomes one into v — so add. Correct precisely because Dijkstra settles each node once.
int countPaths(int n, vector<vector<int>>& roads) { const long long MOD = 1e9 + 7; vector<vector<pair<int,long long>>> adj(n); for (auto& r : roads) { adj[r[0]].push_back({r[1], r[2]}); adj[r[1]].push_back({r[0], r[2]}); } vector<long long> dist(n, LLONG_MAX), ways(n, 0); priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq; dist[0] = 0; ways[0] = 1; // exactly one way to stand still pq.push({0, 0}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // stale for (auto [v, w] : adj[u]) { if (d + w < dist[v]) { // strictly better: replace dist[v] = d + w; ways[v] = ways[u]; pq.push({dist[v], v}); } else if (d + w == dist[v]) { // a tie: accumulate ways[v] = (ways[v] + ways[u]) % MOD; } } } return (int)(ways[n-1] % MOD); }
import heapq def countPaths(n, roads): MOD = 10**9 + 7 adj = [[] for _ in range(n)] for u, v, w in roads: adj[u].append((v, w)) adj[v].append((u, w)) INF = float('inf') dist = [INF] * n ways = [0] * n dist[0], ways[0] = 0, 1 # exactly one way to stand still pq = [(0, 0)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue # stale for v, w in adj[u]: if d + w < dist[v]: # strictly better: replace dist[v] = d + w ways[v] = ways[u] heapq.heappush(pq, (dist[v], v)) elif d + w == dist[v]: # a tie: accumulate ways[v] = (ways[v] + ways[u]) % MOD return ways[n-1] % MOD
Counts overflow 32-bit long before the graph gets large, and C++ overflow is silent — you get a plausible wrong number. Keep ways[] 64-bit and take the modulus at every addition, not once at the end.
The walkthrough for #09 Number of Ways to Arrive at Destination. Watch it, then go straight back and write it yourself.
There is no graph in the input at all. The numbers are the nodes and the allowed multiplications are the edges — and because every multiplication costs one step, this is unit-weight BFS again.
WHAT DO YOU DO WHEN THE GRAPH IS NEVER GIVEN TO YOU?
What plays the role of a node here?
The multipliers are the edges — the operations you may apply. The nodes are the numbers you can be standing on. Getting this backwards is the classic implicit-graph mistake, and it produces a search over 100 items instead of 100000 states.
A student drops the <code>% 100000</code> because 'the numbers are small anyway'. What happens?
The modulus is not an optimisation — it is the definition of the state space. Products grow without bound, so every step reaches a brand-new unvisited value and the queue never drains. The problem is only finite because it is defined mod 100000.
You are given operations rather than edges — multiply by these, add these, flip these — and asked for the fewest operations. The graph is implied by the reachable states.
Let every reachable number be a node and every allowed multiplication an edge of weight 1. Since each step costs the same, BFS finds the fewest steps. The modulus is what makes the node set finite — without it the search never terminates.
int minimumMultiplications(vector<int>& arr, int start, int end) { const int MOD = 100000; if (start == end) return 0; vector<int> dist(MOD, -1); queue<int> q; dist[start] = 0; q.push(start); while (!q.empty()) { int v = q.front(); q.pop(); for (int a : arr) { // multipliers are EDGES int nxt = (int)((1LL * v * a) % MOD); // 1LL: v*a overflows int if (dist[nxt] != -1) continue; dist[nxt] = dist[v] + 1; if (nxt == end) return dist[nxt]; q.push(nxt); } } return -1; }
from collections import deque def minimumMultiplications(arr, start, end): MOD = 100000 if start == end: return 0 dist = [-1] * MOD # nodes are VALUES dist[start] = 0 q = deque([start]) while q: v = q.popleft() for a in arr: # multipliers are EDGES nxt = (v * a) % MOD if dist[nxt] != -1: continue dist[nxt] = dist[v] + 1 if nxt == end: return dist[nxt] q.append(nxt) return -1
The nodes are the numbers, not the multipliers. Searching over the array instead of the value space gives a search of size len(arr) and an answer that is confidently wrong.
Every algorithm so far has needed weights to be non-negative, because each one commits to a distance early. Bellman-Ford commits to nothing: it relaxes every edge, V−1 times, and only then believes the answer. Slower, and the only one that survives a negative edge.
WHAT DO YOU DO WHEN AN EDGE CAN MAKE A PATH CHEAPER?
Why exactly V−1 passes?
A shortest path never repeats a node — repeating one would mean a cycle you could delete for free (or a negative cycle, in which case no shortest path exists). So it touches at most V nodes and therefore at most V−1 edges, and each pass propagates the answer one edge further.
You run one extra pass and something still improves. What does that prove?
After V−1 passes every genuine shortest path has been found. Any further improvement means some route got cheaper by going round again — a negative cycle. Distances there are unbounded below, so the correct response is to report it, not to keep iterating.
A student relaxes every edge without checking <code>dist[u] != INF</code>. What happens?
With INF = 1e9 stored in an int, 1e9 + w can wrap past the 32-bit limit and come out negative — which then looks like a wonderful shortest path and propagates. Guard the relaxation, or use a sentinel with room to spare.
No queue, no settling, no ordering at all. Watch the distance row change under repeated sweeps and then stop changing — that stabilisation is the entire correctness argument.
Negative edge weights, or an explicit ask to detect a negative cycle. The moment weights can be negative, every settle-based algorithm in this deck is off the table and this is what is left.
Give up on ordering entirely. Relax every edge, then do it again, V−1 times. Each pass lets the answer travel one more edge, and a shortest path is at most V−1 edges long — so after V−1 passes nothing genuine is left to find. Anything that improves on a V-th pass can only have come from a negative cycle.
vector<int> bellmanFord(int V, vector<vector<int>>& edges, int src) { const int INF = 1e8; // room to add w without overflowing vector<int> dist(V, INF); dist[src] = 0; for (int pass = 1; pass < V; pass++) // V-1 sweeps for (auto& e : edges) { int u = e[0], v = e[1], w = e[2]; if (dist[u] != INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w; // guard, or INF+w wraps } for (auto& e : edges) { // one more: detection int u = e[0], v = e[1], w = e[2]; if (dist[u] != INF && dist[u] + w < dist[v]) return {-1}; // negative cycle reachable } return dist; }
def bellman_ford(V, edges, src): INF = 10**8 # room to add w without overflowing dist = [INF] * V dist[src] = 0 for _ in range(V - 1): # V-1 sweeps for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: dist[v] = dist[u] + w # guard, or INF+w wraps for u, v, w in edges: # one more: detection if dist[u] != INF and dist[u] + w < dist[v]: return [-1] # negative cycle reachable return dist
Relaxing from an unreachable node is the silent killer: 1e9 + w overflows a 32-bit int to a large negative, which then looks like an excellent path and spreads. Always guard with dist[u] != INF before relaxing.
One run, every pair. The insight is the loop order: k on the outside. After round k, dist[i][j] is the best route using only nodes 1..k as intermediates — so by the last round, every node has been allowed and every pair is optimal.
HOW DO YOU GET EVERY PAIR'S SHORTEST PATH IN ONE RUN?
Why must k be the outermost loop?
Each round must completely finish considering node k before node k+1 is allowed. Put k innermost and you are asking about routes through nodes that have not been fully processed, so values get committed too early. It still runs, still produces a matrix, and the matrix is wrong — the worst kind of bug.
After Floyd finishes on this deck's graph, what is dist[1][8]?
10 — via 1→4→7→8, exactly what Dijkstra settled and exactly what the parent chain reconstructed in unit 06. Three different algorithms, one graph, one answer. 13 is the tempting wrong choice: that was the route via node 5, before it was improved.
When should you prefer Floyd-Warshall over running Dijkstra from every node?
V runs of Dijkstra costs O(V·E log V), which beats O(V³) on sparse graphs. But when E approaches V² the two converge and Floyd's three tight loops win on constants — and if any edge is negative, Dijkstra is not an option at all.
The matrix is the algorithm here, so it replaces the graph. Each round allows one more node as a stopping point. When it finishes, row 1 is identical to what Dijkstra computed on this same graph — three algorithms, one picture, one answer.
You need distances between every pair, the graph is small (n ≤ a few hundred), or weights may be negative. Three nested loops and you are done.
Let dist[i][j] mean the best route from i to j using only nodes 1..k as intermediates. Adding node k+1 to the allowed set can only help via i → k+1 → j, so one comparison updates it. Run k over every node and the restriction disappears entirely.
void floydWarshall(vector<vector<int>>& dist) { int n = dist.size(); const int INF = 1e9; for (int k = 0; k < n; k++) // k FIRST — this is the whole trick for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); for (int i = 0; i < n; i++) if (dist[i][i] < 0) { /* negative cycle through i */ } }
def floyd_warshall(dist): n = len(dist) INF = float('inf') for k in range(n): # k FIRST - this is the whole trick for i in range(n): for j in range(n): if dist[i][k] != INF and dist[k][j] != INF: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] for i in range(n): if dist[i][i] < 0: pass # negative cycle through i
k must be the outermost loop. Reorder it and the code still runs, still fills a matrix, and quietly produces wrong distances — because you are combining routes through nodes that have not been fully processed yet.
The deck's last problem, and it is Floyd-Warshall with one extra step. Compute all pairs, then count per city rather than reading a single distance — the answer is about the shape of the whole matrix.
WHAT DOES AN ALL-PAIRS MATRIX LET YOU ASK THAT ONE RUN CANNOT?
The constraint says n ≤ 100. What does that tell you before you write anything?
Reading the target complexity off the bound is the move this whole deck is trying to teach. n ≤ 100 gives n³ = 10⁶, which is nothing. That single line tells you to stop looking for something clever and write the three-loop solution.
Two cities tie on the smallest neighbour count. Which do you return?
The statement asks for the greatest city number among ties, which is the opposite of the instinct most people have. Iterating upward and using <= on the count handles it naturally; using < keeps the first and quietly fails a subset of cases.
A small n with a threshold and a per-node count. n ≤ 100 in the constraints is the permission slip for O(n³) — stop looking for something cleverer.
Run Floyd-Warshall to get every pairwise distance, then walk each row counting how many cities sit within the threshold. The city with the smallest count wins, and ties go to the greatest city number.
int findTheCity(int n, vector<vector<int>>& edges, int threshold) { const int INF = 1e9; vector<vector<int>> d(n, vector<int>(n, INF)); for (int i = 0; i < n; i++) d[i][i] = 0; for (auto& e : edges) { d[e[0]][e[1]] = e[2]; d[e[1]][e[0]] = e[2]; // undirected: fill both } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i][k] != INF && d[k][j] != INF) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); int best = n + 1, city = -1; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) if (i != j && d[i][j] <= threshold) cnt++; if (cnt <= best) { best = cnt; city = i; } // <= : ties go to the LATER city } return city; }
def findTheCity(n, edges, threshold): INF = float('inf') d = [[INF] * n for _ in range(n)] for i in range(n): d[i][i] = 0 for u, v, w in edges: d[u][v] = w d[v][u] = w # undirected: fill both for k in range(n): for i in range(n): for j in range(n): if d[i][k] + d[k][j] < d[i][j]: d[i][j] = d[i][k] + d[k][j] best, city = n + 1, -1 for i in range(n): cnt = sum(1 for j in range(n) if i != j and d[i][j] <= threshold) if cnt <= best: # <= : ties go to the LATER city best, city = cnt, i return city
The tie-break runs the opposite way to instinct: ties go to the greatest city number. Iterate upward and compare with <= so a later city displaces an earlier one on a tie.
The walkthrough for #13 Find the City With the Smallest Number of Neighbours. Watch it, then go straight back and write it yourself.
Every one of these produces a plausible wrong answer rather than a crash. That is what makes them expensive — the judge tells you no, and the code looks fine.
In Dijkstra a node is settled when it is popped, never when it is pushed. Carry the BFS habit across and node 8 freezes at 13 instead of 10 — with no error anywhere.
Relaxing from an unreachable node wraps 1e9 + w to a large negative, which then looks like a wonderful path and spreads. Guard with dist[u] != INF.
Floyd-Warshall with the loops reordered still runs and still fills a matrix. The matrix is simply wrong, because you combined routes through unfinished nodes.
A direct flight has zero stops and one edge. Looping k times instead of k+1 is the single most common wrong submission on Cheapest Flights.
With a hop limit, each pass must mean exactly one more edge. Write into the live array and one sweep chains several hops together. Snapshot first.
Path counts grow combinatorially. Keep them 64-bit and take the modulus at every addition, not once at the end.
This is the slide to reopen the night before — every algorithm, its cost, and the sentence in the statement that selects it.
Fifteen units, 13 sheet problems, five algorithms that are one idea under different amounts of pressure. If you remember one thing: the algorithm you need is decided by when you are allowed to stop worrying about a distance.
Deck 3 — minimum spanning trees, disjoint set and strongly connected components — is not built yet.
This deck is a fixed 1280 × 720 stage — hand-built animated visualisers, code mirrored beside the graph, problems laid out two columns wide. It scales as one piece, so on this screen the text would land at about 4px. That is not worth shipping to you.
Your progress is saved on this device, so anything you tick on the laptop will be here too.