Implementation design · 001-find-the-shortest-path-between-two
Least-weight shortest path
How we will build it — by hardening a build that already exists.
001-find-the-shortest-path-between-two
Created
Read time
This is a tracer-bullet graduation: the Dijkstra build proven in the exploration is kept
and hardened in place — moved into src/pathfinding/, given a real test suite, and brought under the
project gates. The one live risk is Dijkstra's unsoundness on negative weights, which we fence with an explicit
non-negative-weight assumption rather than absorb.
1 · Principles check
Verify this design respects every principle in v0.1.0. Any violation requires either a principles amendment or a deliberate exception logged below.
| Principle | Compliance | Notes |
|---|---|---|
| P-1 · Clarity over cleverness | A plain linear-scan Dijkstra reads directly; the heap optimisation is deferred rather than smuggled in. | |
| P-2 · Small, reversible changes | One module, one capability; the graduation itself came in as a small reversible step from a quarantined spike. | |
| P-5 · Record the why | The hops-vs-weight decision is grounded in §3 by the archived exploration run, not asserted. | |
| P-6 · Tests accompany behavior | The tracer-bullet's first hardening task is a failing test suite before the code is moved to comply. | |
| P-8 · Library-first boundaries | The finder is a framework-free module with no I/O; tests use the zero-dependency node:test runner. |
2 · Technical context
- Language(s)
- TypeScript, run directly on Node 25 (native type stripping — no build step).
- Frameworks
- None. The domain is deliberately framework-free.
- Architecture
- n/a — a single pure module (
src/pathfinding/), no layering needed. - Storage
- None — operates on an in-memory graph passed by the caller.
- Testing
node:test+node:assert, table-style cases over fixed graphs.- Coverage
- Diff-aware: every path through the finder is exercised by a case; a change never lowers coverage of what it touches.
- Perf targets
- Not a target at this stage; the linear-scan frontier is O(V²). The heap path is deferred (
TBD-heap-frontier). - Constraints
- Non-negative edge weights (licenses Dijkstra over Bellman-Ford).
3 · Grounding & evidence
Every design-bearing fact this design rests on, and how it was confirmed. Because this slice graduated from an
exploration, the headline facts are verified — they were run in the archived spike, and the run
record is preserved (per REQ-LIFECYCLE-006 / 023 FR-004).
| Claim the design rests on | Source | Status | Finding / note |
|---|---|---|---|
| “Shortest” means least weight, not fewest hops — the two diverge on a weighted graph. | explorations/archive/001-find-the-shortest-path-between-two/explore.html §3 run block |
Probe: BFS returned A→C→E (2 hops, cost 25); Dijkstra returned A→B→C→D→E (cost 6). They disagree by 19. | |
| Dijkstra returns the genuine least-weight path on the sample. | explorations/archive/001-find-the-shortest-path-between-two/dijkstra.ts |
The kept build; its output on SAMPLE is A→B→C→D→E, cost 6 — the minimum over all A→E paths. | |
| A linear-scan frontier is sufficient at the sizes in scope. | explorations/archive/001-find-the-shortest-path-between-two/dijkstra.ts |
Correct but O(V²); no large-graph benchmark run. Accepted as a deferred hardening, not a must-tier dependency. |
4 · Approach
Bring the kept build under the gates without rewriting it. Move graph.ts and dijkstra.ts
out of the archive into src/pathfinding/ unchanged in behaviour; drop the probe's inline assertion in favour
of a real node:test suite that pins the exact path and cost (SC-001) and the unreachable case (SC-002). The
discarded BFS arm is not shipped as a code path — it survives only as a test witness that proves fewest-hops and
least-weight genuinely diverge (NFR-001), so the criterion can't silently pass on a graph where any traversal agrees.
5 · Alternatives considered
| Option | Answers “least weight” | Handles neg. weights | Simplicity | Total |
|---|---|---|---|---|
| BFS (fewest hops) | 0 | 0 | 3 | 3 |
| Bellman-Ford | 3 | 3 | 1 | 7 |
| Dijkstra (chosen) | 3 | 0 | 3 | 9 |
BFS is disqualified on the one criterion that matters (it answers hops, not weight — proven in §3). Bellman-Ford
buys negative-weight support the domain doesn't need, at a real simplicity cost; it's the right slice only if
TBD-negative-weights ever lands.
6 · Decisions
D-001 · Dijkstra, not BFS
- Status
Accepted - Context
- The spec's SC-001 demands least weight. The §3 grounding row (archived probe) shows BFS returning a path costing 25 where the true minimum is 6 — a wrong answer, not a slower one.
- Decision
- Ship Dijkstra as the finder. Do not offer BFS as a code path.
- Consequences
- + Correct on every non-negative graph. + Kept build, no rewrite. − Unsound on negative weights (fenced by assumption +
TBD-negative-weights).
D-002 · Linear-scan frontier now, heap later
- Status
Accepted - Context
- The kept build uses a linear scan over the frontier — correct, O(V²). No large-graph workload is in scope (§3, assumed row).
- Decision
- Keep the linear scan. Defer the binary-heap frontier to
TBD-heap-frontier. - Consequences
- + Simplest correct thing (P-1). − Not asymptotically optimal; revisit when a real graph size arrives.
D-003 · node:test, not a test framework
- Status
Accepted - Context
- A pure, dependency-free module (P-8). The spike already ran on bare Node with no toolchain.
- Decision
- Harden with the built-in
node:testrunner andnode:assert; add no test dependency. - Consequences
- + Zero supply-chain surface. − Fewer matchers than a full framework; not needed here.
7 · Project structure
Only the new or changed paths.
src/
pathfinding/
graph.ts # Graph, Edge, cost() — moved from the archive, unchanged
dijkstra.ts # dijkstraPath() — the kept build
tests/
pathfinding.test.ts # node:test — SC-001 exact path/cost, SC-002 unreachable, NFR-001 divergence witness
8 · Risks & mitigations
| Risk | Likelihood | Impact | Mitigation |
|---|---|---|---|
| A caller passes a negative edge weight; Dijkstra returns a wrong path silently. | L | H | Documented non-negative-weight assumption; TBD-negative-weights tracks a guard/Bellman-Ford slice. |
| Linear-scan frontier degrades on a large graph. | M | L | O(V²) is acceptable in scope; TBD-heap-frontier holds the optimisation. |
9 · Complexity tracking
One non-obvious choice worth defending.
Keeping the discarded BFS as a test-only witness is deliberate extra code. It is justified: NFR-001 requires proving the two notions of “shortest” diverge, and the cheapest way to keep that honest is to compute the hop-count path in the test and assert it is more expensive than Dijkstra's — a guard that would catch a graph accidentally simplified until any traversal agrees.
10 · Open questions
None outstanding — the design rests on a run, not an interview, and the deferred work is named in §5 and §8.
11 · Change log
- Initial design, extracted at graduation from exploration 001 (tracer-bullet). §3 seeded with the archived run's verified facts.