Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph where all edge weights are non-negative.

It is a greedy algorithm that always processes the unvisited vertex with the smallest tentative distance next — a decision that is safe precisely because no negative edge can "sneak in" a shorter path later.

The Greedy Insight

Imagine you are navigating a road map. You maintain a running estimate of the cheapest way to reach each city. The key observation: once you finalise a city's distance, it can never improve — because all remaining edges are non-negative, any longer route that has not been explored yet can only make things worse, not better.

This is why a min-heap (priority queue) is used: it always gives us the unfinished city with the smallest current estimate in O(log V) time.

Algorithm Steps

// ── MinHeap helper (binary heap for priority queue) ─────────────────
class MinHeap {
  constructor() { this.heap = []; }

  push([dist, node]) {
    this.heap.push([dist, node]);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  get size() { return this.heap.length; }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent][0] <= this.heap[i][0]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _siftDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.heap[l][0] < this.heap[smallest][0]) smallest = l;
      if (r < n && this.heap[r][0] < this.heap[smallest][0]) smallest = r;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

Full Dijkstra Implementation

// graph: Map<node, Array<[neighbour, weight]>>
// Returns: Map<node, shortest distance from start>
function dijkstra(graph, start) {
  const dist = new Map();
  for (const node of graph.keys()) dist.set(node, Infinity);
  dist.set(start, 0);

  const heap = new MinHeap();
  heap.push([0, start]); // [distance, node]

  while (heap.size > 0) {
    const [d, node] = heap.pop();

    // Stale entry — we already found a better path
    if (d > dist.get(node)) continue;

    for (const [neighbour, weight] of (graph.get(node) || [])) {
      const newDist = d + weight;
      if (newDist < (dist.get(neighbour) ?? Infinity)) {
        dist.set(neighbour, newDist);
        heap.push([newDist, neighbour]);
      }
    }
  }
  return dist;
}

// Example graph
const graph = new Map([
  [0, [[1,4],[2,1]]],
  [1, [[3,1]]],
  [2, [[1,2],[3,5]]],
  [3, []],
]);

const distances = dijkstra(graph, 0);
console.log(distances.get(3)); // 4  (0→2→1→3: 1+2+1)
console.log(distances.get(1)); // 3  (0→2→1: 1+2)

Note

Time: O((V+E) log V) with a binary min-heap. Space: O(V+E). The "stale entry" check (if d > dist.get(node)) handles the fact that JavaScript does not support decreaseKey on a standard heap — we just push duplicate entries and skip outdated ones.

Path Reconstruction

To return the actual path (not just the distance), maintain a prev map tracking which node we came from when we updated each node's distance.

function dijkstraWithPath(graph, start, end) {
  const dist = new Map();
  const prev = new Map();
  for (const node of graph.keys()) { dist.set(node, Infinity); prev.set(node, null); }
  dist.set(start, 0);

  const heap = new MinHeap();
  heap.push([0, start]);

  while (heap.size > 0) {
    const [d, node] = heap.pop();
    if (d > dist.get(node)) continue;
    if (node === end) break; // early exit once target is reached

    for (const [neighbour, weight] of (graph.get(node) || [])) {
      const newDist = d + weight;
      if (newDist < dist.get(neighbour)) {
        dist.set(neighbour, newDist);
        prev.set(neighbour, node);
        heap.push([newDist, neighbour]);
      }
    }
  }

  // Reconstruct path by following prev pointers backwards
  const path = [];
  let current = end;
  while (current !== null) {
    path.unshift(current);
    current = prev.get(current);
  }

  return {
    distance: dist.get(end),
    path: path[0] === start ? path : [], // empty if unreachable
  };
}

const g = new Map([
  [0, [[1,4],[2,1]]],
  [1, [[3,1]]],
  [2, [[1,2],[3,5]]],
  [3, []],
]);
console.log(dijkstraWithPath(g, 0, 3));
// { distance: 4, path: [0, 2, 1, 3] }

Problem 1 — Network Delay Time (LeetCode 743)

There are n network nodes. Given a list of travel times times[i] = [ui, vi, wi], send a signal from node k. Return the minimum time until all nodes receive the signal. If it is impossible, return -1.

This is a direct application of Dijkstra from source k. The answer is the maximum distance in the dist array (the last node to receive the signal).

function networkDelayTime(times, n, k) {
  // Build adjacency list (1-indexed nodes)
  const graph = new Map();
  for (let i = 1; i <= n; i++) graph.set(i, []);
  for (const [u, v, w] of times) graph.get(u).push([v, w]);

  const dist = new Map();
  for (let i = 1; i <= n; i++) dist.set(i, Infinity);
  dist.set(k, 0);

  const heap = new MinHeap();
  heap.push([0, k]);

  while (heap.size > 0) {
    const [d, node] = heap.pop();
    if (d > dist.get(node)) continue;
    for (const [next, w] of graph.get(node)) {
      const nd = d + w;
      if (nd < dist.get(next)) {
        dist.set(next, nd);
        heap.push([nd, next]);
      }
    }
  }

  const maxDist = Math.max(...dist.values());
  return maxDist === Infinity ? -1 : maxDist;
}

console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)); // 2

Problem 2 — Cheapest Flights Within K Stops (LeetCode 787)

Find the cheapest price from src to dst with at most K stops (i.e., at most K+1 edges).

Standard Dijkstra finds the globally cheapest path but ignores the stop limit. The fix: track (cost, node, stopsRemaining) in the heap and only relax if stopsRemaining > 0. Use a dist[node][stops] table or simply let duplicates coexist in the heap.

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

  // dist[node] = min cost to reach node with at most k stops used
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  // [cost, node, stopsLeft]
  // Using array + sort as a simple priority queue
  const heap = [[0, src, k + 1]]; // k stops = k+1 edges

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [cost, node, stopsLeft] = heap.shift();

    if (node === dst) return cost;
    if (stopsLeft === 0) continue;

    for (const [next, price] of graph[node]) {
      const newCost = cost + price;
      // Relax even if newCost > dist[next] — different stop counts may matter
      heap.push([newCost, next, stopsLeft - 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)); // 700  (0→1→3)

Tip

When a constraint like "at most K stops" is added, you can no longer discard states using a simple dist array. Each (node, stopsUsed) pair is a separate state. This is why Bellman-Ford with a fixed number of passes (one per stop) is often cleaner for this specific problem.

Complexity Summary

Operation	With sorted array	With binary min-heap	With Fibonacci heap
Extract min	O(V)	O(log V)	O(log V)
Decrease key / insert	O(1)	O(log V)	O(1) amortised
Overall Dijkstra	O(V²)	O((V+E) log V)	O(E + V log V)

Note

For sparse graphs (E ≈ V), the binary heap is almost always the practical choice. Fibonacci heaps have better theoretical complexity but large constants and complex implementation — they are not used in interviews.

Practice Problems

LeetCode 743 — Network Delay Time
LeetCode 787 — Cheapest Flights Within K Stops
LeetCode 1514 — Path with Maximum Probability
LeetCode 1631 — Path With Minimum Effort
LeetCode 1976 — Number of Ways to Arrive at Destination
LeetCode 2642 — Design Graph With Shortest Path Calculator