Part 13 · Lesson 52 · read
Shortest Paths
BFS when all steps cost the same, Dijkstra for other costs, and Bellman–Ford for limits.
On this page
What a shortest path means
Lesson 50 found the fewest edges between two vertices. An edge is a link between two points (vertices). Real maps are not that simple. Roads have lengths, flights have prices, and network links have delays. When an edge carries a number, we call it a weight (or cost). The shortest path is the route whose weights add up to the smallest total. It can use more edges than another route and still be the shortest.
Which algorithm (set of steps) to use depends on the weights. Equal weights: BFS. Different weights that are never negative: Dijkstra. Negative weights, or a limit on how many edges you may use: Bellman–Ford. The lesson covers them in that order.
BFS when every edge costs the same
BFS (breadth-first search) visits vertices in order of how many edges they are from the start. So the first time it reaches the target, it has found a path with the fewest edges. If every edge costs the same, that is the cheapest path. A grid is the most common case. Each cell is a vertex. Each step to a next-door open cell is an edge of cost 1.
// Fewest steps from the top-left to the bottom-right of a maze. 0 = open, 1 = wall.function shortestPath(maze) { const rows = maze.length, cols = maze[0].length; if (maze[0][0] === 1 || maze[rows - 1][cols - 1] === 1) return -1; const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // -1 = not reached yet dist[0][0] = 0; const queue = [[0, 0]]; let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; if (r === rows - 1 && c === cols - 1) return dist[r][c]; // BFS reaches the goal by its shortest route first for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && maze[nr][nc] === 0 && dist[nr][nc] === -1) { dist[nr][nc] = dist[r][c] + 1; // marking on enqueue, as in lesson 50 queue.push([nr, nc]); } } } return -1;}console.log(shortestPath([[0, 0, 0], [1, 1, 0], [0, 0, 0]])); // 4console.log(shortestPath([[0, 1], [1, 0]])); // -1Two tips from lesson 50. First, mark a cell when you add it to the queue, not when you take it out. Second, move a head number instead of calling queue.shift(). If you also allow diagonal moves, use eight steps instead of four.
A heap in JavaScript
With different weights, the next vertex to process is no longer "the one that has waited longest". It is "the one with the smallest total so far". A priority queue is a line that always gives you the smallest item first. It is usually built on a binary heap. A binary heap is an array kept in a special order: each item is no larger than its two children, so the smallest item is always at the front (item i has children at 2i + 1 and 2i + 2). Adding an item or removing the smallest one costs O(log n). Searching the whole list for the smallest would cost O(n).
JavaScript has no built-in heap. In interviews you are expected to write one, or to say you would use a library. Here is a short one that takes a comparator (a small function that says which of two items goes first). You can paste it into any solution:
// JavaScript has no built-in priority queue, so we write a small binary min-heap.// The comparator works like the one in Array.prototype.sort: negative means "a comes out first".class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } peek() { return this.data[0]; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { // sift up: swap with the parent while smaller const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data; const top = a[0]; const last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { // sift down: swap with the smaller child const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}const pq = new Heap((a, b) => a[0] - b[0]); // entries are [distance, vertex]; smallest distance firstpq.push([7, "E"]); pq.push([2, "B"]); pq.push([5, "C"]); pq.push([1, "A"]);console.log(pq.pop(), pq.pop(), pq.size); // [ 1, 'A' ] [ 2, 'B' ] 2const maxHeap = new Heap((a, b) => b - a); // flip the comparator for a max-heap[3, 9, 4].forEach((x) => maxHeap.push(x));console.log(maxHeap.pop()); // 9Dijkstra's algorithm
Dijkstra's algorithm keeps the best distance found so far, dist[v], for every vertex. At the start every distance is infinity. Then it repeats one step. Take the vertex with the smallest distance and relax its outgoing edges. To relax means: "if going through me to my neighbour is cheaper than what the neighbour has now, update the neighbour."
Why is the vertex we take final? Every other unfinished vertex is at least as far away. Weights are never negative, so a detour through them can only add cost. Nothing can make the vertex we just took any cheaper.
With a heap, we push [distance, vertex] whenever a distance gets better. So a vertex can be in the heap more than once. We do not search for the old entry and delete it, because a plain heap cannot do that cheaply. Instead, when we pop an entry whose distance is larger than dist[v], we know it is stale (out of date) and we skip it. This trick is called lazy deletion.
// Dijkstra: always finalise the unfinished vertex that is closest to the source.function dijkstra(n, edges, src) { // edges: [from, to, weight], directed, weights >= 0 const graph = Array.from({ length: n }, () => []); for (const [a, b, w] of edges) graph[a].push([b, w]); const dist = new Array(n).fill(Infinity); dist[src] = 0; const pq = new Heap((x, y) => x[0] - y[0]); pq.push([0, src]); while (pq.size) { const [d, v] = pq.pop(); if (d > dist[v]) continue; // stale entry: a shorter route to v was found after this was pushed for (const [next, w] of graph[v]) { if (d + w < dist[next]) { dist[next] = d + w; pq.push([dist[next], next]); // lazy deletion: the old entry stays in the heap, we just skip it later } } } return dist;}// (the same Heap class as in the previous section, compacted)class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}const edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]];console.log(dijkstra(5, edges, 0)); // [ 0, 3, 1, 4, 7 ]console.log(dijkstra(3, [[0, 1, 5]], 0)); // [ 0, 5, Infinity ] (vertex 2 is unreachable)There are at most E pushes (E is the number of edges). Each push costs O(log E) = O(log V), where V is the number of vertices. So the total is O((V + E) log V), usually written O(E log V). To get the actual route, also save parent[next] = v whenever you improve dist[next]. Then walk the parents backwards from the target.
Traced: Dijkstra on five vertices
We do not know any distance yet.
▶const dist = new Array(n).fill(Infinity);2dist[src] = 0;3const pq = new Heap((a, b) => a[0] - b[0]);4pq.push([0, src]);5while (pq.size) {6 const [d, v] = pq.pop();7 if (d > dist[v]) continue;8 for (const [next, w] of graph[v]) {9 if (d + w < dist[next]) {10 dist[next] = d + w;11 pq.push([dist[next], next]);12 }13 }14}15return dist;| dist | [Infinity, Infinity, Infinity, Infinity, Infinity] |
Why negative weights break it
The reason above used the idea that "a detour can only add cost". A negative edge lets a detour remove cost. So a vertex we finalised early can still get better later. In the example, vertex 1 looks best at 2 and is finalised. But the longer route 0 → 2 → 1 costs 3 + (−2) = 1.
// The textbook rule "a vertex is final the first time it is popped" is only safe when weights >= 0.function dijkstraNoRevisit(n, edges, src) { const graph = Array.from({ length: n }, () => []); for (const [a, b, w] of edges) graph[a].push([b, w]); const dist = new Array(n).fill(Infinity), done = new Array(n).fill(false); dist[src] = 0; for (let round = 0; round < n; round++) { let v = -1; // simple O(V^2) version: pick the closest unfinished vertex for (let u = 0; u < n; u++) if (!done[u] && (v === -1 || dist[u] < dist[v])) v = u; if (v === -1 || dist[v] === Infinity) break; done[v] = true; // "final": we never look at v again for (const [next, w] of graph[v]) if (!done[next] && dist[v] + w < dist[next]) dist[next] = dist[v] + w; } return dist;}function bellmanFord(n, edges, src) { const dist = new Array(n).fill(Infinity); dist[src] = 0; for (let round = 1; round < n; round++) { let changed = false; for (const [a, b, w] of edges) { if (dist[a] !== Infinity && dist[a] + w < dist[b]) { dist[b] = dist[a] + w; changed = true; } } if (!changed) break; } return dist;}const edges = [[0, 1, 2], [0, 2, 3], [2, 1, -2]]; // the route 0 -> 2 -> 1 costs 3 + (-2) = 1console.log(dijkstraNoRevisit(3, edges, 0)); // [ 0, 2, 3 ] WRONG: vertex 1 is really 1console.log(bellmanFord(3, edges, 0)); // [ 0, 1, 3 ] correctShortest paths on a grid
On a grid, the vertices are cells and the edges go to the four (or eight) neighbours. The cost of one move decides which tool to use:
| The cost of a move | Use | What goes in the queue / heap |
|---|---|---|
| Moves cost 1 each | BFS from the start | queue + a distance grid |
| Entering a cell costs its value | Dijkstra on cells | heap of [cost, row, col] |
| The cost is the biggest height jump (or biggest height) so far | Dijkstra with max() | heap of [worst so far, row, col] |
| 8 directions allowed | the same BFS, with 8 steps | a diagonal step still costs 1 |
Dijkstra does not only work with sums. It works for any path cost that stays the same or grows as the path gets longer. You just replace the "add the edge cost" step with max. For "make the biggest height jump on the way as small as possible", you push [max(worst so far, jump), r, c]. Questions 3 and 6 do exactly this.
Bellman–Ford and limited stops
Bellman–Ford is simpler but slower. Relax every edge, then repeat. After round i, every distance is correct for paths with at most i edges. A shortest path that never visits a vertex twice has at most V − 1 edges. So V − 1 rounds are enough, and it works with negative weights. If one more round still improves something, there is a negative cycle. Counting rounds like this also makes it a good fit for limited stops. Stop after k + 1 rounds and you have the cheapest price that uses at most k + 1 flights.
// Cheapest price from src to dst using at most k stops (that is, at most k + 1 flights).function cheapestWithStops(n, flights, src, dst, k) { let prices = new Array(n).fill(Infinity); prices[src] = 0; for (let round = 0; round <= k; round++) { // round i allows paths of at most i + 1 flights const next = [...prices]; // read from the old array so one round adds exactly one flight for (const [from, to, price] of flights) { if (prices[from] !== Infinity && prices[from] + price < next[to]) next[to] = prices[from] + price; } prices = next; } return prices[dst] === Infinity ? -1 : prices[dst];}const flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]];console.log(cheapestWithStops(4, flights, 0, 3, 1)); // 700 (0 -> 1 -> 3)console.log(cheapestWithStops(4, flights, 0, 3, 2)); // 400 (0 -> 1 -> 2 -> 3, one more stop is cheaper)console.log(cheapestWithStops(4, flights, 0, 3, 0)); // -1 (no direct flight)Notice the copy. Each round reads from prices and writes to next. If you updated one array in place, a single round could chain several flights together and break the stop limit.
Which algorithm?
| Situation | Algorithm | Time |
|---|---|---|
| Every edge costs 1 (or all equal) | BFS | O(V + E) |
| Costs differ, none negative | Dijkstra | O((V + E) log V) |
| Some costs are negative, or there is a limit on the number of edges used | Bellman–Ford | O(V × E), or O(k × E) for k rounds |
| The cost is the largest (or smallest) edge on the path, not the sum | Dijkstra with max/min instead of adding | O((V + E) log V) |
| Costs are only 0 or 1 | 0-1 BFS (with a deque, a list you can add to and remove from at both ends) or Dijkstra | O(V + E) |
If you are not sure, look at the weights. All equal: BFS. Never negative: Dijkstra. Otherwise: Bellman–Ford.
Practice questions
For each problem, decide what the vertices are, what an edge costs, and how a path's cost is combined (sum or max). Then pick BFS, Dijkstra or Bellman–Ford.
In an n × n grid of 0 (open) and 1 (blocked), find the length of the shortest path from the top-left to the bottom-right cell. You may move to any of the 8 neighbouring open cells (sides and corners). The length is the number of cells on the path. Return -1 if there is no path.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Try every path from the top-left that does not repeat a cell. Mark a cell as visited, and remove the mark when you go back (this is called backtracking: make a choice, explore it, then undo the choice and try another). Remember the shortest path that reaches the goal.
function shortestPathBinaryMatrix(grid) { const n = grid.length; if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1; const seen = Array.from({ length: n }, () => new Array(n).fill(false)); let best = Infinity; function dfs(r, c, len) { if (r === n - 1 && c === n - 1) { best = Math.min(best, len); return; } seen[r][c] = true; for (let dr = -1; dr <= 1; dr++) { for (let dc = -1; dc <= 1; dc++) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && !seen[nr][nc]) dfs(nr, nc, len + 1); } } seen[r][c] = false; // un-mark so other paths may use this cell } dfs(0, 0, 1); return best === Infinity ? -1 : best;}console.log(shortestPathBinaryMatrix([[0, 1], [1, 0]])); // 2console.log(shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]])); // 4console.log(shortestPathBinaryMatrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]])); // -1The number of paths in a grid grows extremely fast (exponentially), so this only works on tiny grids. The real limit is n = 100. It is useful to check that your BFS answer is right.
Start from the top-left with length 1. BFS spreads out in rings of equal distance. So the first time it reaches the bottom-right, that distance is the smallest.
function shortestPathBinaryMatrix(grid) { const n = grid.length; if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1; const dist = Array.from({ length: n }, () => new Array(n).fill(0)); dist[0][0] = 1; // 0 doubles as "not reached" const queue = [[0, 0]]; let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; if (r === n - 1 && c === n - 1) return dist[r][c]; for (let dr = -1; dr <= 1; dr++) { for (let dc = -1; dc <= 1; dc++) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && dist[nr][nc] === 0) { dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]); } } } } return -1;}console.log(shortestPathBinaryMatrix([[0, 1], [1, 0]])); // 2console.log(shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]])); // 4console.log(shortestPathBinaryMatrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]])); // -1Each cell enters the queue at most once and checks 8 neighbours. So the time and space are O(n²) for an n × n grid. The case dr = dc = 0 points back at the cell itself. It is already marked, so it is skipped with no harm.
Use BFS whenever every move costs the same. (LeetCode 1091.)
A network has nodes 1..n. Each entry [u, v, w] in times is a one-way link. A signal sent from u reaches v after w time units. A signal starts at node k. Return the time it takes for all nodes to get the signal. Return -1 if some node never gets it.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Work out the shortest distance from k to every node. The answer is the largest of those distances. If any node cannot be reached, the answer is -1.
class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}function networkDelayTime(times, n, k) { const graph = Array.from({ length: n + 1 }, () => []); // nodes are numbered from 1 for (const [u, v, w] of times) graph[u].push([v, w]); const dist = new Array(n + 1).fill(Infinity); dist[k] = 0; const pq = new Heap((a, b) => a[0] - b[0]); pq.push([0, k]); while (pq.size) { const [d, u] = pq.pop(); if (d > dist[u]) continue; for (const [v, w] of graph[u]) { if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); } } } let answer = 0; for (let node = 1; node <= n; node++) answer = Math.max(answer, dist[node]); return answer === Infinity ? -1 : answer;}console.log(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)); // 2console.log(networkDelayTime([[1, 2, 1]], 2, 1)); // 1console.log(networkDelayTime([[1, 2, 1]], 2, 2)); // -1The time is O((V + E) log V). dist starts at Infinity. So if a node cannot be reached, the maximum stays Infinity, and we turn that into -1.
Relax every link (try to make its end node cheaper) again and again, for up to n − 1 rounds. Stop early if a round changes nothing.
function networkDelayTime(times, n, k) { const dist = new Array(n + 1).fill(Infinity); dist[k] = 0; for (let round = 1; round < n; round++) { let changed = false; for (const [u, v, w] of times) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; } } if (!changed) break; } let answer = 0; for (let node = 1; node <= n; node++) answer = Math.max(answer, dist[node]); return answer === Infinity ? -1 : answer;}console.log(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)); // 2console.log(networkDelayTime([[1, 2, 1]], 2, 1)); // 1console.log(networkDelayTime([[1, 2, 1]], 2, 2)); // -1The worst-case time is O(V × E), but the code is short and needs no heap. In JavaScript, Infinity + w is still Infinity. So a node that was never reached cannot give a false improvement.
Dijkstra is good when weights are never negative and the graph can be large. Bellman–Ford is fine for the small limits here (n ≤ 100) and needs no heap. (LeetCode 743.)
You are in the top-left cell of a grid of heights and want to reach the bottom-right cell, moving up, down, left or right. The effort of a route is the biggest height difference (ignoring plus or minus) between two cells next to each other on the route. Return the smallest effort over all routes.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
The "distance" of a cell is the smallest possible worst step on any route to it. Moving to a neighbour gives max(effort so far, this step). Always take the cell with the smallest effort next.
class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}function minimumEffortPath(heights) { const rows = heights.length, cols = heights[0].length; const effort = Array.from({ length: rows }, () => new Array(cols).fill(Infinity)); effort[0][0] = 0; const pq = new Heap((a, b) => a[0] - b[0]); pq.push([0, 0, 0]); while (pq.size) { const [e, r, c] = pq.pop(); if (e > effort[r][c]) continue; if (r === rows - 1 && c === cols - 1) return e; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; const ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); if (ne < effort[nr][nc]) { effort[nr][nc] = ne; pq.push([ne, nr, nc]); } } } return 0;}console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]])); // 2console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]])); // 1console.log(minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]])); // 0The time is O(R × C × log(R × C)). Dijkstra stays correct because max(e, step) ≥ e. Making a route longer never lowers its effort. Weights that are never negative give the same property for sums.
If an effort limit L allows a route, any bigger limit allows it too. So the answers go from "no" to "yes" once and never switch back. Use binary search (halve the range each time) to find the smallest L for which BFS can walk from start to goal using only steps of at most L.
function minimumEffortPath(heights) { const rows = heights.length, cols = heights[0].length; function reachable(limit) { const seen = Array.from({ length: rows }, () => new Array(cols).fill(false)); seen[0][0] = true; const queue = [[0, 0]]; let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; if (r === rows - 1 && c === cols - 1) return true; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc] && Math.abs(heights[nr][nc] - heights[r][c]) <= limit) { seen[nr][nc] = true; queue.push([nr, nc]); } } } return false; } let lo = 0, hi = 1000000; // heights are at most 10^6 while (lo < hi) { const mid = (lo + hi) >> 1; if (reachable(mid)) hi = mid; else lo = mid + 1; } return lo;}console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]])); // 2console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]])); // 1console.log(minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]])); // 0It needs about 20 BFS runs (log₂ of 10⁶), each O(R × C). So the time is O(R × C × log H). This is the same idea as binary searching on the answer in lesson 29: ask a yes/no question, then halve the range.
Dijkstra with max is the more general pattern. The binary-search version needs no heap. It is easy once you spot a "make the maximum as small as possible" problem. (LeetCode 1631.)
There are n cities and flights[i] = [from, to, price] (one-way). Return the cheapest price from src to dst using at most k stops (cities in between). Return -1 if there is no such trip.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
After round i, prices[x] is the cheapest price to reach x with at most i flights. Build each round from a copy of the previous round.
function findCheapestPrice(n, flights, src, dst, k) { let prices = new Array(n).fill(Infinity); prices[src] = 0; for (let round = 0; round <= k; round++) { const next = [...prices]; for (const [from, to, price] of flights) { if (prices[from] !== Infinity && prices[from] + price < next[to]) next[to] = prices[from] + price; } prices = next; } return prices[dst] === Infinity ? -1 : prices[dst];}console.log(findCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)); // 700console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)); // 200console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)); // 500The time is O(k × E) and the space is O(n). The copy is needed. If you updated the same array, one round could chain several flights and go over the stop limit.
Keep a heap of [price, city, stops used]. The first time we pop the destination, its price is the cheapest valid one. Drop entries that use more than k stops. Skip a city if we already popped it with the same or fewer stops. That earlier visit was cheaper and no worse on stops.
class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}function findCheapestPrice(n, flights, src, dst, k) { const graph = Array.from({ length: n }, () => []); for (const [from, to, price] of flights) graph[from].push([to, price]); const fewestStops = new Array(n).fill(Infinity); // fewest stops seen so far when popping each city const pq = new Heap((a, b) => a[0] - b[0]); pq.push([0, src, 0]); while (pq.size) { const [price, city, stops] = pq.pop(); if (city === dst) return price; if (stops >= fewestStops[city] || stops > k) continue; fewestStops[city] = stops; for (const [next, cost] of graph[city]) pq.push([price + cost, next, stops + 1]); } return -1;}console.log(findCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)); // 700console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)); // 200console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)); // 500Each time a city is expanded, it has fewer stops than the last time. So it is expanded at most k + 1 times, and the search stays fast enough. Here stops counts the flights taken so far. The destination is allowed at stops = k + 1, because the last flight lands on it. That is why the test stops > k comes after the destination check.
Bellman–Ford with the copy is the shortest and safest code. It matches the words "at most k edges" exactly. Also know the Dijkstra version, so you can explain why plain Dijkstra fails here. (LeetCode 787.)
Change beginWord into endWord one letter at a time. Every word in between must be in wordList (the begin word does not need to be). Return the number of words in the shortest sequence, counting both ends. Return 0 if there is no such sequence.
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
Build the graph by testing every pair of words to see if they "differ in exactly one place". Then run BFS from the begin word.
function ladderLength(beginWord, endWord, wordList) { const words = [beginWord, ...wordList.filter((w) => w !== beginWord)]; const target = words.indexOf(endWord); if (target === -1) return 0; const oneApart = (a, b) => { let diff = 0; for (let i = 0; i < a.length; i++) if (a[i] !== b[i] && ++diff > 1) return false; return diff === 1; }; const graph = words.map(() => []); for (let i = 0; i < words.length; i++) { for (let j = i + 1; j < words.length; j++) { if (oneApart(words[i], words[j])) { graph[i].push(j); graph[j].push(i); } } } const dist = new Array(words.length).fill(0); dist[0] = 1; const queue = [0]; let head = 0; while (head < queue.length) { const v = queue[head++]; if (v === target) return dist[v]; for (const w of graph[v]) if (dist[w] === 0) { dist[w] = dist[v] + 1; queue.push(w); } } return 0;}console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])); // 5console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"])); // 0Building the graph costs O(N² × L) for N words of length L. This is fine for hundreds of words, but too slow for thousands.
Put the word list in a Set. For a word, go through every position and every letter a–z and make the new word. If the new word is in the Set, it is a neighbour. Remove it from the Set when you add it to the queue. This also works as the visited mark.
function ladderLength(beginWord, endWord, wordList) { const words = new Set(wordList); if (!words.has(endWord)) return 0; const queue = [[beginWord, 1]]; let head = 0; while (head < queue.length) { const [word, steps] = queue[head++]; if (word === endWord) return steps; for (let i = 0; i < word.length; i++) { for (let code = 97; code <= 122; code++) { // 'a' .. 'z' const next = word.slice(0, i) + String.fromCharCode(code) + word.slice(i + 1); if (words.has(next)) { words.delete(next); // visited queue.push([next, steps + 1]); } } } } return 0;}console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])); // 5console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"])); // 0Each word goes into the queue at most once. For each word we try L × 26 new words, and each one costs O(L) to build and look up. So the time is O(N × L² × 26). This beats the pair-by-pair way when N is large and L is small.
First work out, for every word and every position, the pattern with that letter replaced by *. For example hot gives *ot, h*t and ho*. Words that share a pattern are neighbours. Run BFS through the patterns.
function ladderLength(beginWord, endWord, wordList) { const buckets = new Map(); // pattern -> words that match it for (const word of wordList) { for (let i = 0; i < word.length; i++) { const pattern = word.slice(0, i) + "*" + word.slice(i + 1); if (!buckets.has(pattern)) buckets.set(pattern, []); buckets.get(pattern).push(word); } } if (!wordList.includes(endWord)) return 0; const seen = new Set([beginWord]); const queue = [[beginWord, 1]]; let head = 0; while (head < queue.length) { const [word, steps] = queue[head++]; if (word === endWord) return steps; for (let i = 0; i < word.length; i++) { const pattern = word.slice(0, i) + "*" + word.slice(i + 1); for (const next of buckets.get(pattern) || []) { if (!seen.has(next)) { seen.add(next); queue.push([next, steps + 1]); } } } } return 0;}console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])); // 5console.log(ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"])); // 0Building the patterns takes O(N × L²). There are L patterns per word, and each takes O(L) to build. BFS does the same amount of work. This way you do not try 26 letters at each position, which helps most when the alphabet is large.
Any BFS version passes. The 26-letter one is the shortest to write in an interview. The wildcard buckets are the best to explain. Mention the pair-by-pair graph first, as the brute force. (LeetCode 127.)
An n × n grid holds a distinct elevation 0..n²-1 in each cell. At time t the water depth everywhere is t, and you can swim from a cell to a 4-directionally adjacent cell if both elevations are at most t. Starting at the top-left at time 0, return the least time at which you can reach the bottom-right cell.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
The "cost" to reach a cell is the highest elevation seen on the best route to it. Always take the cell with the lowest cost next. Moving to a neighbour costs max(cost so far, neighbour's elevation).
class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}function swimInWater(grid) { const n = grid.length; const best = Array.from({ length: n }, () => new Array(n).fill(Infinity)); best[0][0] = grid[0][0]; const pq = new Heap((a, b) => a[0] - b[0]); pq.push([grid[0][0], 0, 0]); while (pq.size) { const [t, r, c] = pq.pop(); if (t > best[r][c]) continue; if (r === n - 1 && c === n - 1) return t; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; const nt = Math.max(t, grid[nr][nc]); if (nt < best[nr][nc]) { best[nr][nc] = nt; pq.push([nt, nr, nc]); } } } return -1;}console.log(swimInWater([[0, 2], [1, 3]])); // 3console.log(swimInWater([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]])); // 16The time is O(n² log n) for an n × n grid. This is the "minimax path" version of Dijkstra. The cost of a route is its maximum, and making a route longer never lowers it.
If you can swim across at time t, you can also do it at any later time. So the answers switch from "no" to "yes" only once. Use binary search (halve the range each time) to find the smallest t for which BFS over cells with elevation ≤ t connects the two corners.
function swimInWater(grid) { const n = grid.length; function canCross(t) { if (grid[0][0] > t) return false; const seen = Array.from({ length: n }, () => new Array(n).fill(false)); seen[0][0] = true; const queue = [[0, 0]]; let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; if (r === n - 1 && c === n - 1) return true; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] <= t) { seen[nr][nc] = true; queue.push([nr, nc]); } } } return false; } let lo = 0, hi = n * n - 1; // elevations are a permutation of 0 .. n*n-1 while (lo < hi) { const mid = (lo + hi) >> 1; if (canCross(mid)) hi = mid; else lo = mid + 1; } return lo;}console.log(swimInWater([[0, 2], [1, 3]])); // 3console.log(swimInWater([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]])); // 16The time is also O(n² log n). There are about log₂(n²) BFS runs, and each takes O(n²). No heap is needed.
Both are fine. Dijkstra with max is the pattern you can reuse. The binary search is the least code if you do not want a heap. (LeetCode 778. Union-Find in the next lesson is a third way.)
An undirected graph has n nodes. Edge edges[i] works with probability succProb[i]. Given start and end, return the highest probability of success of any path between them. Return 0 if there is no path. (A path works only if every edge on it works, so its probability is all the edge probabilities multiplied together.)
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Keep the best probability found so far for each node. Always take the node with the highest probability next. Update a neighbour with prob × edgeProb if that is higher than the neighbour's current value.
class Heap { constructor(compare) { this.data = []; this.compare = compare; } get size() { return this.data.length; } push(x) { const a = this.data; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.compare(a[i], a[p]) >= 0) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.data, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; while (true) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && this.compare(a[l], a[m]) < 0) m = l; if (r < a.length && this.compare(a[r], a[m]) < 0) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}function maxProbability(n, edges, succProb, start, end) { const graph = Array.from({ length: n }, () => []); edges.forEach(([a, b], i) => { graph[a].push([b, succProb[i]]); graph[b].push([a, succProb[i]]); }); const best = new Array(n).fill(0); best[start] = 1; const pq = new Heap((x, y) => y[0] - x[0]); // largest probability first pq.push([1, start]); while (pq.size) { const [p, v] = pq.pop(); if (v === end) return p; if (p < best[v]) continue; // stale entry for (const [next, q] of graph[v]) { if (p * q > best[next]) { best[next] = p * q; pq.push([best[next], next]); } } } return 0;}console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.2], 0, 2)); // 0.25console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.3], 0, 2)); // 0.3console.log(maxProbability(3, [[0, 1]], [0.5], 0, 2)); // 0The time is O((V + E) log V). The first time the end node is popped, its probability is final, just like a distance in ordinary Dijkstra.
Repeat for up to n − 1 rounds. For every edge, in both directions, improve the neighbour's probability if best[a] × p is higher. Stop when a round changes nothing.
function maxProbability(n, edges, succProb, start, end) { const best = new Array(n).fill(0); best[start] = 1; for (let round = 1; round < n; round++) { let changed = false; edges.forEach(([a, b], i) => { const p = succProb[i]; if (best[a] * p > best[b]) { best[b] = best[a] * p; changed = true; } if (best[b] * p > best[a]) { best[a] = best[b] * p; changed = true; } }); if (!changed) break; } return best[end];}console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.2], 0, 2)); // 0.25console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.3], 0, 2)); // 0.3console.log(maxProbability(3, [[0, 1]], [0.5], 0, 2)); // 0The worst-case time is O(V × E), and no heap is needed. It works because multiplying by a number between 0 and 1 never improves a cycle, so n − 1 rounds are enough.
Write Dijkstra when the graph is big. The Bellman–Ford version is the simplest. In maths, this is the same as making the sum of −log(p) as small as possible, which is an ordinary shortest-path problem. (LeetCode 1514.)
Make it stick
- Say which algorithm to use for equal weights, for weights that are never negative, and for negative weights.
- Write a binary min-heap with a comparator from memory.
- Write Dijkstra with lazy deletion and explain the stale check.
- Explain with an example why a negative edge breaks Dijkstra.
- Explain why Bellman–Ford with k + 1 rounds respects a stop limit, and why it copies the array.
- Turn "make the biggest step as small as possible" into Dijkstra by replacing the sum with max.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Lesson 53 asks a different graph question. It is not "how far?" but "are these two things connected, and what happens when we join them?" The Union-Find structure (a tool that keeps track of groups of connected things) answers this in almost constant time per step.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series