Dijkstra’s Shortest Paths

Start from brute force

The obvious correct approach relaxes every edge, over and over, until no distance changes (Bellman-Ford). It works because a shortest path uses at most V − 1 edges, so V − 1 full passes are enough to carry every distance along it. It costs O(V·E) time and O(V) space. It is too slow because it ignores the one thing this problem promises, that weights are non-negative, and keeps re-relaxing edges out of nodes whose distance is already final. The faster shortcut, a plain BFS that fixes each node the first time it is reached, is wrong: on the first example it gives node 1 distance 4 from the direct edge instead of 3 through node 2.

The approach

With non-negative weights, the unsettled node with the smallest tentative distance can be finalized: any other route to it must leave the settled set through some unsettled node that is already at least as far away, and the remaining edges cannot shorten it. Dijkstra repeats that one step.

The reference keeps an adjacency list adj, tentative distances dist (INF except dist[src] = 0) and a settled flag per node. Each of the n rounds scans for the unsettled u with the smallest dist, marks it settled, and relaxes every (v, w) in adj[u]: if dist[u] + w < dist[v], lower dist[v]. If no unsettled node has a finite distance (u == -1), the rest are unreachable and the loop breaks. Finally every INF becomes -1. The linear scan makes this the array version, the right choice for dense graphs; a binary heap replaces the scan on sparse ones.

Walk through an example

On the first example, settling node 2 at distance 1 is what lowers node 1 from 4 to 3, and node 4 is never reached.

Complexity

The reference’s array version is O(V² + E) time: V rounds that each scan V entries, plus each edge relaxed once. A binary heap with lazy deletion gives O((V + E) log V), better when E is far below V². Both use O(V + E) space for adj and the distances. Bellman-Ford is O(V·E) time and O(V) space.

Edge cases to test

• The source is a sink: dijkstra(3, [[0,1,1],[1,2,1]], 2) returns [-1, -1, 0]. Edges are directed, so nothing flows back from node 2.
• One node, no edges: dijkstra(1, [], 0) returns [0].
• Zero-weight edges are allowed: dijkstra(3, [[0,1,0],[1,2,0]], 0) returns [0, 0, 0]. The algorithm needs w ≥ 0, not w > 0.
• Parallel edges and self-loops: dijkstra(2, [[0,1,5],[0,1,2]], 0) returns [0, 2], and a self-loop such as [0,0,3] never lowers anything. Keep every edge in adj; relaxation picks the cheaper one.
• One negative edge breaks it: with [[0,1,1],[0,2,5],[2,1,-10],[1,3,1]] from node 0, the reference settles node 3 at 2, later lowers node 1 to −5 without re-relaxing its edges, and returns [0, -5, 5, 2]. Bellman-Ford gives [0, -5, 5, -4].

Common mistakes

• Running it on graphs with negative edges — that breaks “settled = final”; use Bellman-Ford instead.
• In the heap version, not skipping stale entries: a node can be pushed several times, and only the copy matching its current distance should be expanded.
• Re-processing settled nodes, or forgetting to mark a node settled when popped.
• Adding both directions for every edge. The edges here are directed; treating them as undirected gives node 2 in the source-is-a-sink case a route back to 0 and 1.

Follow-ups an interviewer asks next

How do you return the shortest path itself?

Keep a parent array. Whenever relaxation lowers dist[v] through u, set parent[v] = u. To rebuild the route to a target, follow parents back to the source and reverse the list. In the first example the route to node 3 is 0 → 2 → 1 → 3, with length 1 + 2 + 1 = 4.

Only one target matters. Can you stop early?

Yes. Return as soon as the target is settled, because a settled distance is final. With a good lower-bound estimate of the remaining distance, A* goes further by ordering the frontier by distance so far plus that estimate. Bidirectional Dijkstra searches from both ends and can stop once the two frontiers’ smallest distances add up to at least the best path found.

What if some weights are negative?

Then a node settled early can later be reached more cheaply, so the invariant fails. Bellman-Ford relaxes every edge V − 1 times in O(V·E) and detects a negative cycle with one extra pass. For all-pairs distances on such a graph, Johnson’s algorithm runs Bellman-Ford once to reweight the edges to non-negative values, then Dijkstra from every source.

All weights are small integers. Anything faster?

If every weight is 0 or 1, 0-1 BFS with a deque runs in O(V + E): push a neighbor reached by a 0-weight edge to the front and one reached by a 1-weight edge to the back. For integer weights up to C, Dial’s algorithm keeps one bucket per distance value and runs in O(V·C + E).

Where this shows up

Shortest path is everywhere: map and road routing, link-state network routing (OSPF), game pathfinding (A* is Dijkstra plus a heuristic), and least-cost dependency analysis. The priority-queue-driven “expand the frontier by cheapest next” pattern generalizes across search.

Reference solution

def dijkstra(n, edges, src):
    INF = float("inf")
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))

    dist = [INF] * n
    dist[src] = 0
    settled = [False] * n

    for _ in range(n):
        u, best = -1, INF                     # pick closest unsettled node
        for i in range(n):
            if not settled[i] and dist[i] < best:
                best, u = dist[i], i
        if u == -1:
            break                              # remaining nodes unreachable
        settled[u] = True
        for v, w in adj[u]:                    # relax outgoing edges
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return [d if d < INF else -1 for d in dist]


print(dijkstra(5, [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], 0))  # -> [0, 3, 1, 4, -1]

function dijkstra(n: number, edges: number[][], src: number): number[] {
  const INF = Infinity;
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);

  const dist = new Array(n).fill(INF);
  dist[src] = 0;
  const settled = new Array(n).fill(false);

  for (let round = 0; round < n; round++) {
    let u = -1, best = INF;                    // closest unsettled node
    for (let i = 0; i < n; i++) {
      if (!settled[i] && dist[i] < best) { best = dist[i]; u = i; }
    }
    if (u === -1) break;                        // rest unreachable
    settled[u] = true;
    for (const [v, w] of adj[u]) {              // relax edges
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
  }
  return dist.map((d) => (d < INF ? d : -1));
}

console.log(dijkstra(5, [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], 0)); // -> [0,3,1,4,-1]