Advanced graph algorithms

Weights break BFS, and knowing why tells you which algorithm to reach for

BFS finds shortest paths because it expands nodes in order of distance — with unit edges, "fewest edges" and "cheapest" are the same thing. Add weights and that guarantee dies: the node one hop away down a cost-100 edge is not closer than a node three hops away down cost-1 edges. Every algorithm in this chapter is a different answer to "how do I restore the expand-in-distance-order property?"

A binary heap you can actually write under pressure

JavaScript has no built-in priority queue, so an interviewer expects you to either write one or state clearly that you would use one. Roughly thirty-five lines, array-backed, items are [priority, value] pairs. (This is the same heap from the heaps chapter — reproduced here because Dijkstra is unwritable without it.)

class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }

  push(item) {
    const a = this.a;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;             // parent index
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }

  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

Dijkstra — the full working version

The invariant: when a node is popped from the heap with the smallest tentative distance, that distance is final. Nothing still in the heap can improve it, because every remaining path leaves through a node that already costs at least as much and all edge weights are non-negative — that last clause is exactly why Dijkstra breaks on negative edges.

// adj[u] = array of [v, weight]. Non-negative weights only. O((V + E) log V).
function dijkstra(n, adj, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  const pq = new MinHeap();
  pq.push([0, src]);

  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (d > dist[u]) continue; // STALE entry: we already found a better route to u — skip it

    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (nd < dist[v]) {      // relaxation: this route to v beats anything known
        dist[v] = nd;
        pq.push([nd, v]);      // push a NEW entry rather than decrease-key
      }
    }
  }
  return dist;
}

Dry run: dijkstra(4, adj, 0) on the S–A–B–T graph above (S=0, A=1, B=2, T=3)

T is pushed twice — once at cost 100 straight off S, once at cost 3 through A then B — and the heap pops the cheap entry first purely because it's smaller. The expensive entry is still sitting in the heap; the d > dist[u] guard on pop 5 is what discards it instead of re-relaxing from a node whose distance is already final.

A textbook Dijkstra uses decrease-key to update a node's priority in place. A binary heap can't do that in O(log n) without an index map, so the standard trick is lazy deletion: push a duplicate entry and discard outdated ones on pop via the d > dist[u] guard. The heap holds up to E entries instead of V, which is why the complexity is usually written O(E log V) — same thing, since log E ≤ 2 log V.

Recovering the actual path costs one extra array:

const parent = new Array(n).fill(-1);
// inside the relaxation, alongside dist[v] = nd:
parent[v] = u;

function reconstruct(parent, target) {
  const path = [];
  for (let at = target; at !== -1; at = parent[at]) path.push(at);
  return path.reverse();
}

Same loop, different cost: path probability and the bottleneck

Dijkstra works because of two properties of "cost", and neither says the cost has to be a sum. First, extending a path never makes it better: adding a non-negative edge can only raise the total. Second, partial paths can be compared, so the heap can order them. Anything that satisfies both can be run through the same loop. Two variants come up often enough to know by heart.

Maximum probability. "Each undirected edge succeeds with some probability; find the path from start to end with the highest chance of every edge succeeding." Probabilities multiply along a path, and since every factor is at most 1, extending a path never raises its probability. That is the same shape as a non-negative edge weight, with × in place of + and "largest" in place of "smallest". The heap pops the smallest key, so push the negated probability.

function maxProbability(n, edges, succProb, start, end) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b], i) => {
    adj[a].push([b, succProb[i]]);
    adj[b].push([a, succProb[i]]);
  });

  const best = new Array(n).fill(0); // best[v] = highest probability found so far; 0 = unreached
  best[start] = 1;
  const pq = new MinHeap();
  pq.push([-1, start]); // the heap pops the smallest key, so store the NEGATED probability

  while (pq.size > 0) {
    const [negP, u] = pq.pop();
    const p = -negP;
    if (p < best[u]) continue; // stale: a better route to u was found after this entry was pushed
    if (u === end) return p;   // the first pop of the target is final
    for (const [v, chance] of adj[u]) {
      const np = p * chance;   // probabilities multiply, and a factor of at most 1 never raises it
      if (np > best[v]) {
        best[v] = np;
        pq.push([-np, v]);
      }
    }
  }
  return 0;
}

Dry run: edges 0-1 (0.5), 1-2 (0.5), 0-2 (0.2); from 0 to 2

The two-edge route wins over the direct edge even though it has more edges. Time is O((V + E) log V), as for ordinary Dijkstra. Taking logarithms turns the product into a sum of -log p values, which are non-negative: that is why this is a shortest-path problem in disguise.

Bottleneck (minimax) path. "Find the path whose largest edge is as small as possible": the lowest bridge you must cross, the narrowest road, the hardest step of a hike. The cost of a path is the maximum along it, and extending a path can only keep the maximum or raise it, so the first property holds again. Replace d + w with Math.max(d, w) and everything else stays.

function minimaxPath(n, adj, src, dst) {
  const best = new Array(n).fill(Infinity); // best[v] = smallest possible "largest edge" on a path to v
  best[src] = 0;
  const pq = new MinHeap();
  pq.push([0, src]);

  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (d > best[u]) continue;
    if (u === dst) return d;
    for (const [v, w] of adj[u]) {
      const nd = Math.max(d, w); // the only change from Dijkstra: combine with max instead of +
      if (nd < best[v]) {
        best[v] = nd;
        pq.push([nd, v]);
      }
    }
  }
  return Infinity;
}

Dry run: edges 0-3 (9), 0-1 (4), 1-2 (4), 2-3 (4); from 0 to 3

The ordinary shortest path from 0 to 3 is the direct edge of weight 9, but the bottleneck path takes the three edges of weight 4. This is the engine behind "Path With Minimum Effort" (the grid version in the exercises). Binary search on the answer with a connectivity check also works, and so does Kruskal's algorithm, because the path between two nodes inside a minimum spanning tree is a bottleneck-optimal path (the minimum spanning tree chapter covers why).

Counting shortest paths, and the second shortest

Two questions piggyback on the same distances. How many shortest paths are there? (This is "Number of Ways to Arrive at Destination", and the answer is requested modulo 10⁹ + 7.) Keep a second array, ways[v]. When a strictly shorter route to v is found, every old path is now too long, so ways[v] = ways[u]. When a route ties the best known, every shortest path to u extends to a new shortest path to v, so ways[v] += ways[u].

Why is ways[u] final when u is popped? Every shortest path to u comes through a predecessor that is strictly closer, because edge weights are positive, so all of u's predecessors were popped and contributed their counts before u. A zero-weight edge breaks that argument, so this version needs positive weights.

function countShortestPaths(n, roads) {
  const MOD = 1_000_000_007;
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of roads) {
    adj[u].push([v, w]);
    adj[v].push([u, w]);
  }

  const dist = new Array(n).fill(Infinity);
  const ways = new Array(n).fill(0); // ways[v] = number of shortest paths from node 0 to v
  dist[0] = 0;
  ways[0] = 1;
  const pq = new MinHeap();
  pq.push([0, 0]);

  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        ways[v] = ways[u];                    // a strictly better route: forget the old count
        pq.push([nd, v]);
      } else if (nd === dist[v]) {
        ways[v] = (ways[v] + ways[u]) % MOD;  // a tie: every shortest path to u extends to v
      }
    }
  }
  return ways[n - 1];
}

Dry run: the 7-node example with roads 0-6 (7), 0-1 (2), 1-2 (3), 1-3 (3), 6-3 (3), 3-5 (1), 6-5 (1), 2-5 (1), 0-4 (5), 4-6 (2)

The answer is 4. Note the order of the pops at distance 5: any order among equal distances gives the same counts, because each of those nodes has all of its own predecessors at strictly smaller distances.

The second shortest. "Find the second shortest path length, strictly longer than the shortest" is Dijkstra with two distances per node. Keep d1[v], the shortest, and d2[v], the shortest value strictly larger than d1[v]. A new candidate nd falls in one of three cases: it beats d1 (the old best is demoted to d2), it lies strictly between the two (it replaces d2), or it is useless. Each node may now be expanded twice, once per value it keeps, so the stale test compares against d2, not d1.

function secondShortest(n, adj, src, dst) {
  const d1 = new Array(n).fill(Infinity); // shortest distance to each node
  const d2 = new Array(n).fill(Infinity); // shortest distance that is strictly longer than d1
  d1[src] = 0;
  const pq = new MinHeap();
  pq.push([0, src]);

  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (d > d2[u]) continue; // neither the best nor the second best way to reach u
    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (nd < d1[v]) {
        d2[v] = d1[v]; // the old best becomes the runner-up (its heap entry is still pending)
        d1[v] = nd;
        pq.push([nd, v]);
      } else if (nd > d1[v] && nd < d2[v]) {
        d2[v] = nd;
        pq.push([nd, v]);
      }
    }
  }
  return d2[dst];
}

Dry run: edges 0-1 (1), 1-2 (1), 0-2 (3); from 0 to 2

The answer is d2[2] = 3, the direct edge. Walks may revisit a node: d2[0] = 2 is the walk 0 → 1 → 0. The version that asks for a second shortest simple path is a harder problem and needs a different algorithm. Time is O((V + E) log V) with a constant factor of about two.

When "shortest" has a second constraint: Cheapest Flights Within K Stops

This one is a trap for pure Dijkstra: the cheapest way to reach a node might use too many stops, while a pricier route is still viable. The state is (node, stopsUsed), not node — and once you see that, the cleanest solution is a bounded Bellman-Ford: relax all edges exactly k + 1 times.

function findCheapestPrice(n, flights, src, dst, k) {
  let dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  for (let round = 0; round <= k; round++) {  // k stops = k+1 edges
    const next = dist.slice();               // SNAPSHOT — see the warning below
    for (const [u, v, price] of flights) {
      if (dist[u] === Infinity) continue;
      if (dist[u] + price < next[v]) next[v] = dist[u] + price;
    }
    dist = next;
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}

The same flights problem, with Dijkstra on (node, flights taken)

The bounded Bellman-Ford above is not the only way. The root of the trap is that "the cheapest cost to reach a node" is the wrong state, because a cheap arrival with many flights may be useless later while a dearer arrival with few flights still has room. So make the state what the problem actually constrains: (node, flights taken so far). Now "cheapest cost to reach this state" is a well-defined quantity, and Dijkstra applies to the graph of states, where each flight leads from (u, t) to (v, t + 1).

function findCheapestPrice(n, flights, src, dst, k) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, price] of flights) adj[u].push([v, price]);

  const best = Array.from({ length: n }, () => new Array(k + 2).fill(Infinity)); // best[node][flightsTaken]
  best[src][0] = 0;
  const pq = new MinHeap();
  pq.push([0, src, 0]); // [cost so far, node, flights taken]

  while (pq.size > 0) {
    const [cost, u, taken] = pq.pop();
    if (u === dst) return cost;             // cheapest way to reach dst within the limit
    if (cost > best[u][taken]) continue;    // stale
    if (taken === k + 1) continue;          // k stops = k + 1 flights: none left to take
    for (const [v, price] of adj[u]) {
      const nc = cost + price;
      if (nc < best[v][taken + 1]) {
        best[v][taken + 1] = nc;
        pq.push([nc, v, taken + 1]);
      }
    }
  }
  return -1;
}

Because the first time the target is popped it is at its cheapest cost under the limit, the function returns immediately. There are at most n · (k + 2) states and each is expanded once, so the time is about O(k · E · log(k · E)). That is slower than Bellman-Ford's O(k · E) here, but the augmented-state idea is the one that carries over to harder limits (fuel tanks, keys collected, discounts remaining), where Bellman-Ford's round structure no longer fits.

Why the table has a second index: flights 0→1 (1), 1→2 (1), 2→3 (1), 0→2 (5); from 0 to 3, at most 1 stop

Bellman-Ford — negative weights, and detecting a negative cycle

Bellman-Ford abandons the heap entirely: it just relaxes every edge, V − 1 times. After i rounds, every shortest path using at most i edges is correct, and a simple path can't use more than V − 1 edges — so V − 1 rounds finish the job. That reasoning is also the negative-cycle detector: if a V-th round still improves something, no finite shortest path exists.

// edges = [[u, v, w], ...] directed. Returns dist array, or null if a negative cycle is reachable.
// O(V · E) time, O(V) space.
function bellmanFord(n, edges, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i < n - 1; i++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] === Infinity) continue;   // unreachable: skip, never relax from here
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break;                    // early exit: a settled round means we're done
  }

  // One extra round. Any further improvement means a reachable negative cycle.
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) return null;
  }
  return dist;
}

To identify which nodes are affected rather than just detecting the cycle, run a final BFS/DFS from every node that improved in the extra round and mark everything reachable as −∞. That's the version asked for in arbitrage-detection questions ("is there a sequence of currency trades that multiplies your money?" — take -log(rate) as the weight and a negative cycle is exactly an arbitrage).

SPFA: Bellman-Ford that only looks where something changed

Plain Bellman-Ford relaxes every edge every round, even edges out of nodes whose distance has not changed since the last round. Those edges cannot improve anything, so relaxing them is wasted work. SPFA, the "shortest path faster algorithm", keeps a queue of nodes whose distance just changed and relaxes only the edges out of those. When a node's distance improves it joins the queue, unless it is already waiting there.

Negative cycles need a new test, since the "extra round" is gone. Track, for every node, how many edges its current best path uses. A shortest path without a cycle uses at most n - 1 edges, so if some node's best path ever reaches n edges the path repeats a node and the repeated stretch is a cycle that keeps lowering the distance: a negative cycle.

function spfa(n, adj, src) {
  const dist = new Array(n).fill(Infinity);
  const edgesOnPath = new Array(n).fill(0); // edges on the best path currently known to each node
  const inQueue = new Array(n).fill(false);
  const queue = new Array(n);                // circular buffer: a node is in it at most once
  let head = 0, tail = 0;

  dist[src] = 0;
  queue[tail++ % n] = src;
  inQueue[src] = true;

  while (head !== tail) {
    const u = queue[head++ % n];
    inQueue[u] = false;
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        edgesOnPath[v] = edgesOnPath[u] + 1;
        if (edgesOnPath[v] >= n) return null; // a shortest path with n edges repeats a node: negative cycle
        if (!inQueue[v]) {
          inQueue[v] = true;
          queue[tail++ % n] = v;
        }
      }
    }
  }
  return dist;
}

Dry run: edges 0→1 (4), 0→2 (5), 1→2 (-3), 2→3 (2), 1→3 (6)

Node 2 was reached twice, first at 5 and then at 1 through the negative edge, but it was expanded only once, after its distance settled, because the first queue entry covered both. That sharing is the saving.

Floyd-Warshall — all pairs, in three loops

Sometimes the question isn't one source but every pair ("shortest path between all cities," "transitive closure," "find the city with the fewest reachable neighbours"). Floyd-Warshall answers it in three nested loops with one idea: consider intermediate nodes one at a time. After processing k, the table holds shortest paths that may only route through nodes 0..k.

// O(V^3) time, O(V^2) space. Handles negative edges; d[i][i] < 0 means a negative cycle.
function floydWarshall(n, edges) {
  const d = Array.from({ length: n }, () => new Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) d[i][i] = 0;
  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w); // min guards against parallel edges

  for (let k = 0; k < n; k++) {              // k MUST be the outermost loop
    for (let i = 0; i < n; i++) {
      if (d[i][k] === Infinity) continue;    // prune a whole row — a real constant-factor win
      for (let j = 0; j < n; j++) {
        const viaK = d[i][k] + d[k][j];
        if (viaK < d[i][j]) d[i][j] = viaK;
      }
    }
  }
  return d;
}

V³ sounds fatal but the constant factor is tiny and there's no heap — up to roughly V = 400-500 it beats running Dijkstra V times in practice, and it is vastly easier to get right. It's also the go-to for reachability: swap min/+ for OR/AND and you have transitive closure.

Floyd-Warshall: recovering the path, not just the length

The distance matrix tells you how far; interviews often ask for the route. Keep a second matrix next[i][j], the first node to step to when travelling from i to j on a best path. Initially next[u][v] = v for each edge. When going through k improves d[i][j], the new best path starts the same way as the best path from i to k, so next[i][j] = next[i][k]. To print a route, start at i and repeat i = next[i][j] until you arrive.

function floydPaths(n, edges) {
  const d = Array.from({ length: n }, () => new Array(n).fill(Infinity));
  const next = Array.from({ length: n }, () => new Array(n).fill(-1)); // next[i][j] = first step on a best path i -> j
  for (let i = 0; i < n; i++) {
    d[i][i] = 0;
    next[i][i] = i;
  }
  for (const [u, v, w] of edges) {
    if (w < d[u][v]) {
      d[u][v] = w;
      next[u][v] = v;
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (d[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
          next[i][j] = next[i][k]; // to go i -> j through k, start the way you start towards k
        }
      }
    }
  }
  return { d, next };
}

function pathBetween(next, i, j) {
  if (next[i][j] === -1) return [];
  const path = [i];
  while (i !== j) {
    i = next[i][j];
    path.push(i);
  }
  return path;
}

Dry run: edges 0→1 (5), 1→2 (3), 2→3 (1), 0→3 (10)

Reading the route from 0 to 3: next[0][3] is 1, next[1][3] is 2, next[2][3] is 3, so the path is 0 → 1 → 2 → 3 with total 9, cheaper than the direct edge of 10. Storing the whole path in each cell would cost O(V) per update and O(V⁴) in total; the next matrix keeps the total at O(V³) time and O(V²) space.

0-1 BFS — when weights are only 0 and 1

A heap is overkill when there are only two possible edge costs. Use a deque: relaxing along a 0-weight edge doesn't change the distance, so push that node on the front; a 1-weight edge pushes to the back. The deque stays sorted by distance automatically — it only ever holds two distinct values, d and d+1 — giving true O(V + E) with no log factor. This shows up in grid problems like "minimum obstacles to remove" or "minimum cost to make a path" (rotating grid arrows is free in the direction it points, costs 1 otherwise).

// Two-stack deque: amortized O(1) at both ends, no O(n) Array#shift.
class Deque {
  constructor() { this.front = []; this.back = []; }
  get size() { return this.front.length + this.back.length; }
  pushFront(x) { this.front.push(x); }
  pushBack(x) { this.back.push(x); }
  popFront() {
    if (this.front.length === 0) {
      while (this.back.length > 0) this.front.push(this.back.pop()); // reverse back onto front, amortized O(1)
    }
    return this.front.pop();
  }
}

// adj[u] = [[v, w]] with every w either 0 or 1. O(V + E).
function zeroOneBFS(n, adj, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  const dq = new Deque();
  dq.pushBack(src);

  while (dq.size > 0) {
    const u = dq.popFront();
    for (const [v, w] of adj[u]) {
      const nd = dist[u] + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        if (w === 0) dq.pushFront(v); // same distance layer — must be processed before any d+1 node
        else dq.pushBack(v);          // next layer
      }
    }
  }
  return dist;
}

Multi-source BFS — seed the queue with everything at once

"Distance from each cell to the nearest gate / zero / rotten orange" looks like V separate BFS runs. It isn't. Push every source into the queue at distance 0 before the loop starts and run one ordinary BFS — the frontiers expand together and the first time any source reaches a cell is, by definition, the nearest source. One pass, O(V + E), no repetition.

// 01 Matrix: distance from each cell to the nearest 0. One BFS, all zeros seeded.
function updateMatrix(mat) {
  const R = mat.length, C = mat[0].length;
  const dist = Array.from({ length: R }, () => new Array(C).fill(-1));
  const queue = [];

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (mat[r][c] === 0) { dist[r][c] = 0; queue.push(r * C + c); } // ALL sources seeded before the loop
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let head = 0; head < queue.length; head++) { // index-based queue: no O(n) shift()
    const cell = queue[head];
    const r = (cell / C) | 0, c = cell % C;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (dist[nr][nc] !== -1) continue;           // already reached by a nearer (or equal) source
      dist[nr][nc] = dist[r][c] + 1;
      queue.push(nr * C + nc);
    }
  }
  return dist;
}

The same seeding trick makes "Rotting Oranges" a one-liner change (track the last distance assigned and verify no fresh orange is left as −1), and it generalizes: a multi-source Dijkstra is just pushing every source at its own starting cost. Any time you'd write "run X from every source, take the min," check whether one seeded run does it.

Shortest and longest paths on a DAG

The table at the end of this chapter says that on a DAG, topological order beats everything. Here is the code and the reason. Process the nodes in topological order. When you reach node u, every edge into u comes from a node earlier in the order, so every candidate for dist[u] has already been offered and dist[u] is final. Relax the edges out of u and move on. Each edge is relaxed once, so the time is O(V + E), whatever the weights are: negative edges are fine, and so is longest path, which is hard on a general graph (the longest simple path is NP-hard) but needs only the comparison flipped here.

function dagPaths(n, edges, src) {
  const adj = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);
    indegree[v]++;
  }

  const order = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) order.push(i);
  for (let head = 0; head < order.length; head++) { // Kahn's algorithm; order doubles as the queue
    for (const [v] of adj[order[head]]) {
      if (--indegree[v] === 0) order.push(v);
    }
  }
  if (order.length < n) return null; // a cycle: there is no topological order

  const shortest = new Array(n).fill(Infinity);
  const longest = new Array(n).fill(-Infinity);
  shortest[src] = 0;
  longest[src] = 0;

  for (const u of order) { // every edge into u was relaxed before u is processed
    for (const [v, w] of adj[u]) {
      if (shortest[u] !== Infinity && shortest[u] + w < shortest[v]) shortest[v] = shortest[u] + w;
      if (longest[u] !== -Infinity && longest[u] + w > longest[v]) longest[v] = longest[u] + w;
    }
  }
  return { shortest, longest };
}

Dry run: edges 0→1 (2), 0→2 (-1), 1→3 (3), 2→3 (4), 2→4 (1), 3→5 (-2), 4→5 (6); source 0

The shortest path to node 5 costs 1, through 0 → 2 → 3 → 5 (that is -1 + 4 - 2 = 1), and the longest costs 6, through 0 → 2 → 4 → 5 (that is -1 + 1 + 6 = 6). Notice that node 3 was first set to 5 from node 1 and improved to 3 from node 2, both before node 3 was processed.

Dijkstra without a heap: the array version for dense graphs

The heap makes Dijkstra O(E log V), which is a win when E is near V and a loss when the graph is dense. If E is about V², then E log V is about V² log V, and a plain array does better: at each of the V rounds, scan all V nodes for the unfinished one with the smallest distance (O(V)), finalize it, and relax its V possible neighbours (O(V)). That is O(V²) in total with no heap, no stale entries and no duplicates.

function denseDijkstra(n, w, src) {
  const dist = new Array(n).fill(Infinity);
  const done = new Array(n).fill(false);
  dist[src] = 0;

  for (let round = 0; round < n; round++) {
    let u = -1;
    for (let i = 0; i < n; i++) {
      if (!done[i] && (u === -1 || dist[i] < dist[u])) u = i; // linear scan replaces the heap
    }
    if (u === -1 || dist[u] === Infinity) break;              // everything left is unreachable
    done[u] = true;
    for (let v = 0; v < n; v++) {
      if (!done[v] && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
    }
  }
  return dist;
}

Use it when the input is already an adjacency matrix (a distance table, a complete graph over points) and V is a few thousand at most: the V × V matrix is then the input size, so O(V²) is linear in what you were given. The correctness argument is the same as for the heap version, since "the unfinished node with the smallest distance" is exactly what the heap's pop returns. Choosing between the two is a one-line comparison: V² against E log V. It is also the form Prim's algorithm takes on a dense graph in the next chapter.

A-star: Dijkstra with a compass

Dijkstra explores in a growing disc around the source, in every direction, because it knows nothing about where the target is. When you have one source, one target and a cheap way to estimate the remaining distance, you can bias the search toward the target. A* orders the heap by f = g + h, where g is the cost paid so far and h(v) is a heuristic: a guess of the cost from v to the target. With h = 0 it is exactly Dijkstra.

The guess has to be honest. Admissible means h never overestimates the true remaining cost, and then the first time the target is popped its cost is optimal. On a grid with 4-direction moves of cost 1, the Manhattan distance |dr| + |dc| is admissible, since no path can be shorter than the straight-line count of steps. It is also consistent (it drops by at most 1 per step, which is the step cost), and with a consistent heuristic every node is finalized the first time it is popped, so the same stale-entry skip as Dijkstra's is enough.

function aStarGrid(grid, start, goal) {
  const R = grid.length, C = grid[0].length;
  const [sr, sc] = start, [gr, gc] = goal;
  if (grid[sr][sc] === 1 || grid[gr][gc] === 1) return -1;

  const h = (r, c) => Math.abs(r - gr) + Math.abs(c - gc); // Manhattan distance: never overestimates on a 4-way grid
  const cost = Array.from({ length: R }, () => new Array(C).fill(Infinity));
  cost[sr][sc] = 0;
  const pq = new MinHeap();
  pq.push([h(sr, sc), 0, sr, sc]); // [f = steps so far + estimate, steps so far, row, column]
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  while (pq.size > 0) {
    const [, steps, r, c] = pq.pop();
    if (steps > cost[r][c]) continue;
    if (r === gr && c === gc) return steps;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C || grid[nr][nc] === 1) continue;
      if (steps + 1 < cost[nr][nc]) {
        cost[nr][nc] = steps + 1;
        pq.push([steps + 1 + h(nr, nc), steps + 1, nr, nc]);
      }
    }
  }
  return -1;
}

Dry run: a 3 × 5 grid with a wall, from (0,0) to (0,4)

. . . . .
. # # # .
. . . . .

A* expanded 5 cells. Dijkstra on the same grid expands up to 9, since it also fills in the cells behind and beside the start at distances 1, 2 and 3 before it reaches distance 4. The gap grows with the grid: on an open 9 × 9 grid with the goal along the top row, A* expands 9 cells and Dijkstra up to 45. The worst case is no better than Dijkstra's, though. If the heuristic is poor, or the way to the target is a long detour around a wall, A* explores as widely as Dijkstra does.

Bidirectional search: two small circles instead of one big one

In an unweighted graph where each node has about b neighbours, a BFS to distance d visits on the order of b^d nodes. Two searches, one from the source and one from the target, each only need to reach distance d / 2 before they touch. That is about 2 · b^d/2 nodes, a very large saving when b is big and d is moderate. It is the standard speed-up for "Word Ladder" and other puzzle-state graphs, whose branching factor is large.

The mechanics: keep a distance map and a frontier for each side. Each round, expand one whole level of the smaller frontier (so the work stays balanced). While scanning neighbours, if a neighbour is already in the other side's map, the two searches have met, and the answer is distance so far + 1 + the other side's distance.

function bidirectionalBFS(adj, source, target) {
  if (source === target) return 0;
  const distA = new Map([[source, 0]]); // distances from the source
  const distB = new Map([[target, 0]]); // distances from the target
  let frontA = [source], frontB = [target];

  while (frontA.length > 0 && frontB.length > 0) {
    const fromA = frontA.length <= frontB.length; // always expand the smaller frontier
    const front = fromA ? frontA : frontB;
    const mine = fromA ? distA : distB;
    const other = fromA ? distB : distA;
    const next = [];

    for (const u of front) {
      for (const v of adj[u]) {
        if (other.has(v)) return mine.get(u) + 1 + other.get(v); // the two searches touch
        if (!mine.has(v)) {
          mine.set(v, mine.get(u) + 1);
          next.push(v);
        }
      }
    }
    if (fromA) frontA = next;
    else frontB = next;
  }
  return -1;
}

Dry run: path 0-1-2-3-4-5-6 with extra leaves 7, 8 on node 1 and 9 on node 5; from 0 to 6

The searches met in the middle and the answer is the length of the whole path. Returning at the first meeting is right: before each level, the two searches have not touched, which means the true distance is at least the sum of their radii plus one, and any meeting found while expanding that level has length at most that sum, so it is exactly the shortest. If you instead stop one level too early or too late the answer is off by one or two.

Picking the right one

That last row is the one candidates forget. On a DAG you can relax edges in topological order and get shortest or longest paths in linear time, negative weights included — no heap, no V·E. If the problem says "no cycles" or the edges encode a strict ordering (course prerequisites, build steps, DP-shaped grids), check for the DAG shortcut before reaching for Dijkstra.

Recognizing it in an unseen problem

• "Minimum cost/time/effort to get from A to B" with numbers on the edges → shortest path. The words "cost," "time," "price," "signal delay," and "effort" are all weight synonyms.
• The weights are all 1, or the problem is on an unweighted grid → plain BFS. Do not reach for Dijkstra; it's strictly more code for the same answer, and interviewers notice.
• Exactly two distinct weights (usually 0 and 1) → 0-1 BFS with a deque. "Free in this direction, costs 1 to change" is the tell.
• Any negative number appears, or there's a cap on the number of edges used → Bellman-Ford. A hop limit turns the state into (node, hops), which Bellman-Ford's round structure gives you for free.
• V is small (≤ 400) and the question asks about every pair, or you need to answer many source-target queries → Floyd-Warshall, and mention the O(V³)/O(V²) trade explicitly.
• "Nearest X for every cell" → multi-source BFS, seeded with all X. If you find yourself writing a loop that runs BFS once per source, stop and seed instead.
• "Highest probability," "largest/smallest bottleneck," "narrowest road" → the Dijkstra loop with a different combine step: multiply and pop the largest, or take the max along the path.
• "How many shortest paths" or "the second shortest" → Dijkstra carrying a count, or two distances per node.
• A second limit on the path (stops, fuel, removals) → put it in the state and run Dijkstra on (node, used), not on node alone.
• The graph is a DAG (or the problem says "no cycles") → relax in topological order for shortest or longest paths in O(V + E).
• Dense graph or an adjacency matrix as input → array-scan Dijkstra in O(V²); one source, one target on a grid with coordinates → A* with an admissible heuristic; huge branching, undirected → bidirectional BFS.
• Pitfalls: Dijkstra with negative edges (wrong, and quietly so); sorting an array as a fake priority queue (TLE); Floyd-Warshall with k not outermost (wrong); relaxing from an unreachable node when the sentinel is a finite number like 10⁹ (the sum looks like a real distance; with Infinity it stays infinite, but the guard keeps the intent clear); and using Array#shift() as a queue on 10⁵ nodes (O(n²) hidden inside an O(V+E) algorithm).