Shortest Path (Weighted)

How to think about it

When edges have weights, BFS (which counts hops) no longer gives the shortest path, a two-hop route through cheap edges can beat a one-hop expensive edge. Dijkstra is the workhorse: maintain a dist[] array and a min-priority queue keyed by distance. Pop the closest unvisited node, relax its edges (if dist[u] + w < dist[v], update dist[v] and push). Each node is finalized once, the first time it is popped, so you never need to revisit it.

The constraint: Dijkstra requires non-negative weights. A negative edge can pull a “finalized” node’s distance lower after it was popped, invalidating the greedy invariant. For graphs with negative edges (or to detect negative cycles), use Bellman-Ford: relax every edge V-1 times; a V-th pass that still relaxes indicates a negative cycle.

Template shapes

Shape	Core move	Example
Dijkstra	Min-heap by dist; relax on pop	LC 743, LC 1976
Dijkstra + state	State = (node, extra dim); heap keyed by composite dist	LC 787 (k-stops), LC 2045
Binary search on answer + BFS	Feasibility check on a threshold	LC 1631
Bellman-Ford	Relax all edges V-1 times	(when negative edges)

Complexity baseline

Dijkstra with a binary heap: O((V + E) log V) time, O(V) space. Bellman-Ford: O(VE) time, O(V) space. For dense graphs a naive O(V²) Dijkstra (no heap) can be simpler and competitive.

From template to problem

1. Confirm weights are non-negative; if not, reach for Bellman-Ford.
2. Build an adjacency list of (neighbor, weight) pairs.
3. Seed dist[source] = 0, push (0, source); all others Infinity.
4. Pop the min; skip if stale (dist mismatch); relax neighbors.
5. After the loop, dist[dest] is the answer, or -1 if still Infinity (unreachable).
6. If the problem adds a constraint (k-stops, discounts), extend the state, not the algorithm.

/**
 * Shortest path template: Dijkstra from a source over an adjacency list.
 *
 * NOTE: This uses `pq.sort + shift` as a toy priority queue for readability.
 * In interviews / production, use a binary heap (O((V+E) log V)); this version
 * is O(V² log V) due to the per-step sort. Algorithm and logic are identical.
 */

export function dijkstra(
  n: number, edges: [number, number, number][], source: number,
): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, w] of edges) {
    adj[a]!.push([b, w]);
    adj[b]!.push([a, w]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  dist[source] = 0;

  const pq: [number, number][] = [[0, source]];
  while (pq.length) {
    // Toy PQ: sort + shift. Replace with a binary heap for O((V+E) log V).
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (dist[u]! + w < dist[v]!) {
        dist[v] = dist[u]! + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  return dist;
}

/**
 * Shortest path template: Dijkstra from a source over an adjacency list.
 *
 * NOTE: This uses `pq.sort + shift` as a toy priority queue for readability.
 * In interviews / production, use a binary heap (O((V+E) log V)); this version
 * is O(V² log V) due to the per-step sort. Algorithm and logic are identical.
 */

export function dijkstra(
  n: number, edges: [number, number, number][], source: number,
): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, w] of edges) {
    adj[a]!.push([b, w]);
    adj[b]!.push([a, w]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  dist[source] = 0;

  const pq: [number, number][] = [[0, source]];
  while (pq.length) {
    // Toy PQ: sort + shift. Replace with a binary heap for O((V+E) log V).
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (dist[u]! + w < dist[v]!) {
        dist[v] = dist[u]! + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  return dist;
}