jsschools

Dijkstra's Algorithm

Finds shortest paths from a source to all reachable nodes in a graph with non-negative edge weights using a greedy approach and a priority queue.

Spec ↗

Syntax

dijkstra(graph, src)

Parameters

NameTypeRequiredDescription
graph Map<number, Array<{to: number, w: number}>> Yes Weighted adjacency list. Each entry maps a node to an array of `{to, w}` objects where `w` is the non-negative edge weight.
src number Yes Source node. Distance from src to itself is 0.

Returns

Map<number, number> — Shortest distance from src to every reachable node.

Examples

// Min-heap using a sorted array (for clarity; use a real heap for large graphs)
function dijkstra(graph, src) {
  const dist = new Map();
  dist.set(src, 0);
  // [distance, node]
  const pq = [[0, src]];

  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    if (d > (dist.get(u) ?? Infinity)) continue;
    for (const { to, w } of graph.get(u) ?? []) {
      const nd = d + w;
      if (nd < (dist.get(to) ?? Infinity)) {
        dist.set(to, nd);
        pq.push([nd, to]);
      }
    }
  }
  return dist;
}

const g = new Map([
  [0, [{to:1,w:4},{to:2,w:1}]],
  [1, [{to:3,w:1}]],
  [2, [{to:1,w:2},{to:3,w:5}]],
  [3, []],
]);
console.log([...dijkstra(g, 0)]);
Output 
[ [ 0, 0 ], [ 2, 1 ], [ 1, 3 ], [ 3, 4 ] ]

// Verify: shortest path 0→1→3 costs 4+1=5? No: 0→2→1→3 costs 1+2+1=4
const g = new Map([
  [0, [{to:1,w:4},{to:2,w:1}]],
  [1, [{to:3,w:1}]],
  [2, [{to:1,w:2},{to:3,w:5}]],
  [3, []],
]);
function dijkstra(graph, src) {
  const dist = new Map([[src, 0]]);
  const pq = [[0, src]];
  while (pq.length) {
    pq.sort((a,b) => a[0]-b[0]);
    const [d, u] = pq.shift();
    if (d > (dist.get(u)??Infinity)) continue;
    for (const {to,w} of graph.get(u)??[]) {
      const nd = d+w;
      if (nd < (dist.get(to)??Infinity)) { dist.set(to,nd); pq.push([nd,to]); }
    }
  }
  return dist;
}
console.log(dijkstra(g, 0).get(3)); // 0→2→1→3 = 4
Output 
4

Notes

| Case | Time | Space | |---------|---------------------|-------| | Best | O((V + E) log V) | O(V) | | Average | O((V + E) log V) | O(V) | | Worst | O((V + E) log V) | O(V) | With a proper binary min-heap or Fibonacci heap (O(E + V log V)). The array-based priority queue above runs in O(V²) due to sorting — use a real min-heap for production. **Critical invariant**: all edge weights must be non-negative. For negative weights, use Bellman-Ford. Dijkstra is single-source; for all-pairs shortest paths use Floyd-Warshall.

See also