219: Shortest Paths I: Unweighted BFS and Dijkstra

Learning outcomes

By the end of this lesson, you can:

explain and apply unweighted shortest path in a realistic implementation;
explain and apply path reconstruction in a realistic implementation;
explain and apply dijkstra invariant in a realistic implementation;
explain and apply relaxation in a realistic implementation;
explain and apply priority queue duplicates in a realistic implementation.

Prerequisites and retrieval

This lesson builds on the 01–06 foundation and the earlier lessons in this module. Before you start, retrieve one concrete example from a previous project where you had to make a similar choice: finding the nearest reachable item, keeping track of how you got somewhere, or processing work in priority order. That retrieval is useful because shortest-path algorithms are less about memorizing a loop than about matching an algorithm to its constraints.

The target is twofold: you should be able to reason about an interview-sized problem and about a production data-processing problem. In both cases, begin with the requirements and constraints, then choose the algorithm whose invariant you can defend.

Terminology

Unweighted shortest path: BFS visits vertices in nondecreasing order of edge count. Therefore, in an unweighted graph, the first time it discovers a vertex is the shortest distance from the source.
Path reconstruction: Record a predecessor or parent when a vertex is discovered or its distance is improved. Starting at the target, follow those links back to the source and reverse the collected sequence.
Dijkstra invariant: Once the unsettled vertex with the smallest tentative distance is extracted, that distance is final, provided every edge weight is nonnegative.
Relaxation: For an edge u->v with weight w, compare dist[u]+w with dist[v]. If the new route is smaller, update the distance and the predecessor.
Priority queue duplicates: If the priority queue has no decrease-key operation, insert a new (distance, vertex) entry whenever a distance improves. When an entry is popped, skip it if its distance is stale.
Complexity: With adjacency lists and a binary heap, Dijkstra is commonly O((V+E) log V). Dense graphs may benefit from a different representation or implementation, so the graph shape still matters.

Mental model

Treat Shortest Paths I: Unweighted BFS and Dijkstra as a design problem, not as a pair of code templates. The inputs, outputs, invariant, and failure modes should all be visible. Edge weights determine the choice: BFS is the right model for unit-cost edges, while Dijkstra handles nonnegative weights by using a priority queue to settle the smallest tentative distance.

A good implementation also makes its assumptions explicit. It should narrow uncertainty at the boundary and leave enough evidence, such as tests, types, constraints, metrics, or diagrams, to show why the design is safe. This is particularly useful when a graph comes from external data and its shape or weights cannot simply be assumed.

A practical sequence for both interviews and production work is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not begin with a library call or a familiar snippet. State what must remain true first. The mechanism comes afterward, chosen because it enforces that invariant rather than because it is the shortest code.

Deep dive

1. Unweighted shortest path

The first question is whether every edge has the same cost. If it does, a route with fewer edges is always at least as good as a route with more edges, and BFS gives you the shortest distance without maintaining weighted priorities. BFS discovers vertices in nondecreasing edge count, so the first discovery of a vertex gives its shortest distance from the source.

This guarantee depends on the graph really being unweighted, or on every edge having the same unit cost. If different weights matter, counting edges is not enough; use a weighted shortest-path algorithm instead.

Decision rule: Use unweighted shortest path deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

2. Path reconstruction

A distance array answers “how far is the target?” but not “which route did the algorithm take?” To answer the second question, store the predecessor when you first discover a vertex in BFS, or when relaxation improves its best-known distance. Once the search reaches the target, walk from target to source through those predecessor links, collect the vertices, and reverse the sequence.

There is a useful separation here: distances describe the result's cost, while predecessors describe the evidence for the route. If the target was never discovered, reconstruction must report that no path exists rather than attempting to follow an absent chain.

Decision rule: Use path reconstruction deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

3. Dijkstra invariant

Dijkstra is appropriate when edge weights are nonnegative. It repeatedly extracts the unsettled vertex with the smallest tentative distance. At that point, no alternative route through another unsettled vertex can produce a smaller distance, so the extracted distance is final. This is the Dijkstra invariant.

The restriction on negative edges is not a minor implementation detail. A negative edge can make a vertex look final and then provide a cheaper route later, which breaks the proof. If negative weights are valid, Dijkstra is the wrong algorithm and its priority-queue behavior cannot repair the reasoning.

Decision rule: Use dijkstra invariant deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

4. Relaxation

Relaxation is the small operation that improves a route when a better one is found. For an edge u->v with weight w, test whether dist[u]+w < dist[v]. If so, replace dist[v] and record u as the predecessor of v.

That comparison is intentionally strict: an equal-cost route does not need to replace the route already recorded unless the product has a separate tie-breaking requirement. Relaxation is the core primitive in several shortest-path algorithms, so being able to state its condition precisely makes the larger algorithm easier to inspect and debug.

Decision rule: Use relaxation deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

5. Priority queue duplicates

Many binary-heap implementations do not support decrease-key. When relaxation finds a shorter route, the straightforward alternative is to push a second (distance, vertex) entry. The queue may then contain several entries for the same vertex, but that is safe if popped entries are checked against the current distance.

An entry is stale when its stored distance is greater than the best distance currently recorded for that vertex. Skip such an entry. Without this check, the algorithm may repeat work or incorrectly treat an older route as current. The duplicate-entry approach trades some extra queue entries for a simpler and widely available heap interface.

Decision rule: Use priority queue duplicates deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

6. Complexity

For adjacency lists and a binary heap, Dijkstra commonly runs in O((V+E) log V). The logarithmic factor comes from heap operations, and the graph terms reflect visiting vertices and considering edges. The exact bound also depends on how many queue entries improvements create and on the heap implementation.

This is not a universal “best” representation. Dense graphs can make an adjacency matrix or a simpler selection strategy reasonable, while sparse graphs usually benefit from adjacency lists. State the graph size and density before choosing an implementation, and measure if the real workload is large enough for the distinction to matter.

Decision rule: Use complexity deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

Worked example

Consider an interview-sized problem alongside a production data-processing problem. The same algorithm may be useful in both, but the constraints and failure handling will not necessarily be the same. Start by writing the requirement in one sentence, list the input and output contracts, and map each possible failure mode to the concept that owns it.

The key design move is separation. Parsing and validation belong at the boundary. Domain rules belong in the domain or service layer. Persistence rules belong in the database or repository. Presentation rules belong in the client. Mixing those concerns can make a happy-path demo look shorter, but it makes edge cases and operational failures much harder to reason about.

For an unweighted graph, the distance array and queue make the BFS invariant concrete: a vertex is queued when it is first discovered, and its distance is one greater than the distance of the vertex that discovered it.

type Edge = readonly [to: number, weight: number];
type Graph = readonly Edge[][];

function bfs(graph: Graph, start: number): number[] {
  const distance = Array(graph.length).fill(-1);
  const queue = [start];
  distance[start] = 0;
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i]!;
    for (const [next] of graph[node]!) {
      if (distance[next] !== -1) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }
  return distance;
}

The weight field is present in the graph type, but BFS intentionally ignores it. That is a useful review signal: this function is valid only when the graph's edge weights are unit costs, or when the caller has deliberately chosen to treat all edges as unweighted. A weighted implementation must use the weight during relaxation, typically with Dijkstra when the weights are nonnegative.

Walk the example through at least four cases: a normal reachable path, an empty or missing value, a duplicate, retry, or concurrent path where that distinction is relevant, and a dependency failure. For every case, say which layer detects the problem and what the caller observes. That exercise exposes assumptions that a happy-path trace hides, and it is the level of reasoning expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies a bottleneck or a meaningful risk.

When the topic involves an external dependency, define both timeout and cancellation behavior. When it involves persistence, define transaction and consistency expectations. When it produces user-visible state, define loading, empty, error, stale, and success states. When security is involved, assume the client can be modified and all network input is untrusted. For graph processing specifically, also consider malformed vertex IDs, invalid weights, unexpectedly large graphs, and memory consumed by queued work.

Guided lab

Implement unweighted BFS path reconstruction and Dijkstra with a heap. Add a negative edge and use it to demonstrate exactly why Dijkstra's proof fails, rather than merely repeating the restriction. The point of the lab is to connect the implementation to the invariant and then observe the boundary where the invariant no longer applies.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

Edge cases and failure modes

Unweighted shortest path: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Path reconstruction: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Dijkstra invariant: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Relaxation: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Priority queue duplicates: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern may be syntactically correct while being architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path, then discovering the real contracts during integration.
Optimizing before measuring, or choosing a scalable mechanism when no scale requirement justifies its complexity.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

When debugging, reproduce the smallest failing graph or input first. Inspect the actual values, queue entries, and execution path. Trace the boundary where the invariant first becomes false: was a vertex marked too early, was a stale priority entry processed, or was a negative weight accepted? Fix the owning layer instead of adding a downstream patch that merely hides the symptom.

Interview questions

What problem does Unweighted shortest path solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Path reconstruction solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Dijkstra invariant solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Relaxation solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Priority queue duplicates solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Shortest Paths I: Unweighted BFS and Dijkstra to another developer in five minutes. Include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. A strong explanation should make clear not only which algorithm you chose, but also which assumption makes that choice valid.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.