Dijkstra's Shortest Path

Implement Dijkstra's algorithm with a min-heap priority queue to find single-source shortest paths in O((V+E) log V) on graphs with non-negative edge weights.

6 min read Level 3/5 #dsa#graph#dijkstra

What you'll learn

Implement Dijkstra's algorithm with a priority queue in JavaScript
Explain why negative edge weights break Dijkstra's correctness
Reconstruct the shortest path from source to any vertex

Dijkstra’s algorithm finds the shortest path from a single source to all other vertices in a weighted graph, provided no edge has a negative weight. It is the backbone of GPS routing, network packet forwarding, and game pathfinding.

How It Works

Set dist[source] = 0; all other distances start at Infinity.
Use a min-heap to always process the vertex with the smallest known distance next.
For each extracted vertex, relax its outgoing edges: if dist[u] + weight < dist[v], update dist[v] and push [dist[v], v] into the heap.
Repeat until the heap is empty.

JavaScript’s standard library has no built-in min-heap, so we simulate one with a sorted array for clarity. In production, use a proper heap or the heap npm package.

// graph: Map<number, Array<{to: number, weight: number}>>
function dijkstra(graph, numVertices, source) {
  const dist = new Array(numVertices).fill(Infinity);
  const prev = new Array(numVertices).fill(null);
  dist[source] = 0;

  // Min-heap: [distance, vertex]
  const heap = [[0, source]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]); // O(E log E) — use a real heap in prod
    const [d, u] = heap.shift();

    if (d > dist[u]) continue; // stale entry

    for (const { to: v, weight: w } of graph.get(u) ?? []) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        prev[v] = u;
        heap.push([newDist, v]);
      }
    }
  }
  return { dist, prev };
}

function getPath(prev, target) {
  const path = [];
  for (let cur = target; cur !== null; cur = prev[cur]) path.push(cur);
  return path.reverse();
}

// Weighted graph: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (5), 2→3 (8)
const g = new Map([
  [0, [{ to: 1, weight: 4 }, { to: 2, weight: 1 }]],
  [1, [{ to: 3, weight: 5 }]],
  [2, [{ to: 1, weight: 2 }, { to: 3, weight: 8 }]],
  [3, []],
]);

const { dist, prev } = dijkstra(g, 4, 0);
console.log(dist);         // [0, 3, 1, 8]
console.log(getPath(prev, 3)); // [0, 2, 1, 3]

Why Negative Weights Break Dijkstra

Once a vertex is extracted from the heap its distance is considered final. A negative edge arriving later could lower that distance, invalidating the assumption. Use Bellman-Ford when negative weights are present.

Complexity

Structure	Time complexity	Space
Array (naive)	O(V²)	O(V)
Binary min-heap	O((V+E) log V)	O(V)
Fibonacci heap	O(E + V log V)	O(V)

The binary min-heap version is the standard choice and dominates in competitive programming and interviews.

Up Next

When edge weights can be negative, Dijkstra fails — Bellman-Ford handles that case and also detects negative cycles.

Bellman-Ford Algorithm →