Dijkstra and 0-1 BFS: When Not to Use a Heap

Shortest path is not one algorithm. It is a family, and the weight set picks the member.

- Every edge weight is the same (usually 1): BFS, a queue. First time you reach a node is optimal. - Every edge weight is 0 or 1: 0-1 BFS, a deque. Zero-weight goes to the front, one-weight to the back. - Weights are non-negative and otherwise unrestricted: Dijkstra. A heap (or an O(n²) scan) extracts the closest unsettled node. - Negative weights: Dijkstra is wrong. Bellman-Ford (or a DAG DP) — not this lesson.

The heap is not a personality trait. If you reach for priority_queue on a maze of unit steps, you are running Dijkstra on a graph BFS already solves in linear time.

0-1 BFS — deque, not priority_queuejs

function bfs01(n, adj, src) {
  // adj[u] = [[v, w], ...] with w === 0 or w === 1
  const dist = Array(n).fill(Infinity);
  dist[src] = 0;
  const dq = [src]; // 0-weight to the front, 1-weight to the back
  while (dq.length) {
    const u = dq.shift();
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (w === 0) dq.unshift(v);
        else dq.push(v);
      }
    }
  }
  return dist;
}

TRACE

Nodes 0–3. Edges 0→1 weight 0, 0→2 weight 1, 1→3 weight 1, 2→3 weight 0. 0-1 BFS from 0.

Deque [0], dist[0]=0

Pop 0. Edge 0→1 (w=0): dist[1]=0, push_front 1. Edge 0→2 (w=1): dist[2]=1, push_back 2. Deque: [1, 2].

0-weight to the front

1 / 3

Dijkstra — non-negative weights, heap (binary heap sketched)js

function dijkstra(n, adj, src) {
  const dist = Array(n).fill(Infinity);
  dist[src] = 0;
  const heap = [[0, src]]; // [dist, node], fake heap: scan min
  const popMin = () => {
    let i = 0;
    for (let k = 1; k < heap.length; k++) if (heap[k][0] < heap[i][0]) i = k;
    return heap.splice(i, 1)[0];
  };
  while (heap.length) {
    const [d, u] = popMin();
    if (d !== dist[u]) continue; // stale
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Grids: if a step is always cost 1, grid BFS (see Grid Shortest Path and the Shortest Maze game). If some moves cost 0 (ice, conveyor, 'stay free') and others cost 1, 0-1 BFS on the cells. If terrain has arbitrary positive costs, Dijkstra on the cells.

Negative edge? Heap Dijkstra can 'finalize' a node too early. Do not patch it with hacks; switch algorithm.

CHECK

Maze, every 4-dir step costs 1. Which structure?

CHECK

Edges have weight 0 (portal) or 1 (walk). You need distances from s. Heap?

Checks 0/2

Next lesson