Dijkstra's shortest path

Shortest distance from one node to all others when edges have non-negative weights.

How it works

Keep a best-known distance for every node, starting at infinity, and 0 for the source. A min heap always gives the closest unfinished node. For each neighbour, if going through this node is shorter, update and push. Because weights are non-negative, the first time a node comes off the heap its distance is final. Skip stale heap entries.

Reach for it when

• Weighted shortest path: cost, time, distance
• Cheapest route, lowest latency path

Copy// edges [u, v, w]: directed, non-negative weights. Returns shortest distance to every node.
function dijkstra(n, edges, src) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const pq = new MinHeap((a, b) => a[0] - b[0]); // [distance, node]
  pq.push([0, src]);
  while (pq.size) {
    const [d, u] = pq.pop();
    if (d > dist[u]) continue; // stale entry, already found shorter
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Traps

• Negative weights break it (use Bellman-Ford).
• Not skipping stale entries wastes work, and on some problems gives wrong answers.
• With all weights equal, plain BFS is simpler and faster.