Dijkstra's Shortest Path Pattern

When to use Dijkstra's Shortest Path

• The graph has weighted edges and all weights are non-negative.
• You need the shortest path (or the shortest-path distance) from a single source to one or all other nodes.
• Plain BFS would give wrong answers because edge weights are not all equal.
• The problem can be modeled as a graph where states are nodes and transitions carry a cost — including grid problems where moves have different costs.
• You need the minimum total cost (time, distance, effort) to reach a target, not just whether the target is reachable.

Template

function dijkstra(numNodes, edges, source) {
  const graph = Array.from({ length: numNodes }, () => []);
  for (const [from, to, weight] of edges) {
    graph[from].push([to, weight]);
  }
  const dist = new Array(numNodes).fill(Infinity);
  dist[source] = 0;
  const heap = [[0, source]];
  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, node] = heap.shift();
    if (d > dist[node]) continue;
    for (const [next, weight] of graph[node]) {
      const nd = d + weight;
      if (nd < dist[next]) {
        dist[next] = nd;
        heap.push([nd, next]);
      }
    }
  }
  return dist;
}

Common mistakes

• Running Dijkstra on a graph with negative edge weights — it silently returns wrong answers because the greedy 'closest unvisited' invariant breaks the moment a future edge can decrease an already-settled distance.
• Forgetting the stale-entry skip (`if (d > dist[node]) continue;`) and re-relaxing neighbors of an outdated heap entry, which inflates the runtime to O(V^2 log V) on dense graphs.
• Marking a node as visited the moment it is pushed onto the heap instead of when it is popped, which prevents legitimate shorter paths from being processed.
• Initializing the distance array with 0 or undefined instead of Infinity, so the first relaxation never fires for unreachable nodes.
• Using a regular FIFO queue instead of a min-heap — this is BFS, not Dijkstra, and works only when all edge weights are equal.