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. Fifteen 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;
}

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();
}

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];
}

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: Infinity + w must not propagate
      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).

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.

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.

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.
• 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); adding to Infinity from an unreachable node (poisons the table); and using Array#shift() as a queue on 10⁵ nodes (O(n²) hidden inside an O(V+E) algorithm).