Specification · 001-find-the-shortest-path-between-two
Least-weight shortest path
Given a weighted graph and two nodes, return the path of least total weight — which is not, in general, the path of fewest hops.
dijkstraPath(graph, start, goal) and get back the least-total-weight node path, or null when the goal is unreachable.
Read time
A small pathfinding library that returns the least-total-weight path between two nodes of a weighted graph. Graduated from an exploration whose one job was to settle an ambiguity: on a weighted graph, “shortest” can mean fewest hops or least weight, and the two diverge. The spike proved they diverge sharply — so this spec commits to weight, and to a build (Dijkstra) that was kept, not rebuilt.
- I Independent
- Depends only on the project principles. No upstream specs; the graph type is owned here.
- N Negotiable
- Outcomes only — “least total weight, unreachability reported distinctly.” The algorithm choice (Dijkstra) and the frontier structure are the design's to defend.
- V Valuable
- Unlocks SC-001 — a caller gets the genuinely cheapest route, not a hop-count lookalike.
- E Estimable
- The build already exists (tracer-bullet); the design back-fills and hardens it. No open interview blocks estimation.
- S Small
- One capability, four functional requirements, one module. Well under the budget.
- T Testable
- Every requirement is observable on a fixed graph; the headline criterion is an exact path and cost.
- Exec / PM
- §Context, §User scenarios, §Success criteria.
- Reviewer
- §Requirements, §Assumptions, §Open questions.
- Implementer
- §Requirements, §Data model, §Conformance index.
1 · Context
“Find the shortest path between two nodes” is under-specified the moment edges carry weight. Breadth-first search answers fewest hops; Dijkstra answers least total weight. On an unweighted graph they coincide, so the ambiguity hides — until a weighted graph pulls them apart.
This spec was not written up-front. It was graduated from an exploration
(explorations/archive/001-find-the-shortest-path-between-two/) that built both algorithms loosely and ran
them head-to-head to find out which one the phrase actually means. The build answered it, so the answer is grounded
in a run, not an argument. The consumer is any caller that needs the cheapest route through a weighted graph.
2 · User scenarios & testing
Each story MUST be independently testable: if you implemented only US1, you would still have a viable MVP.
US1 · The cheapest route, not the shortest-looking one P1
As a caller with a weighted graph, I want to get the path of least total weight between two nodes so that I follow the genuinely cheapest route, even when it takes more hops.
Acceptance: on a graph where the fewest-hops path and the least-weight path differ, the function returns the least-weight one, and its summed weight is no greater than any other path's.
Edge cases
- Unreachable goal — no path exists from start to goal; the function reports that distinctly rather than returning a partial or empty path that reads as cost 0.
- Start equals goal — the path is the single node, total weight 0.
- Ties — two paths share the minimum weight; returning either is correct (no stable-tie guarantee is promised).
3 · Requirements
Conformance keywords (
Functional
Given a weighted graph, a start node, and a goal node, the finder
Rationale
This is the whole point the exploration settled: “shortest” means least weight. A fewest-hops answer is a defect, not an alternative.
When no path exists between start and goal, the finder null result), never a wrong or empty path.
When start equals goal, the finder
The finder cost() helper that sums a path's weight, so a
caller can independently confirm the returned path's total.
Non-functional
Correctness
Out of scope (deferred to other slices)
- Negative edge weights — Dijkstra is unsound with them; that case needs Bellman-Ford and its own slice.
- A priority-queue (binary-heap) frontier — a performance hardening for large graphs; the linear-scan frontier is correct but not asymptotically optimal.
- Enumerating the k shortest paths, or all minimum-weight paths under a tie.
4 · Data model
Only the entities this feature owns.
Entities
- Graph
- An adjacency map: each node maps to its list of outgoing edges. Undirected graphs are built by linking both directions.
- Edge
{ to: Node, weight: number }— a non-negative weight to a neighbouring node.- Path
- An ordered list of nodes from start to goal, or
nullwhen unreachable.
Invariant: the returned path's summed cost() is ≤ the cost of any other start→goal path. Weights are assumed non-negative (see Assumptions); a negative weight would break this invariant and is out of scope.
5 · Success criteria
Technology-agnostic, measurable outcomes. These are how we know it worked.
On the sample weighted graph, the shortest path from A to E is
A → B → C → D → E at total weight 6 — and specifically not the fewest-hops path
A → C → E, whose weight is 25.
Querying a goal with no connecting path returns null (not an empty or partial path).
6 · Assumptions
Edge weights are non-negative — the domain (distances, costs, latencies) makes this safe, and it is what licenses Dijkstra over Bellman-Ford.
Graphs are small enough that a linear-scan frontier is acceptable; the heap optimisation is deferred, not forgotten.
7 · Open questions
None outstanding — the one ambiguity this feature carried (hops vs. weight) was resolved empirically by the exploration before the spec existed.
8 · Conformance index
Auto-built from every <spec-requirement> in this document.
9 · Change log
- Graduated from exploration 001 (tracer-bullet). Initial Draft extracted from the kept build.