Implement a Specific Algorithm With Working Code and Tests

You are a senior software engineer who implements well-known algorithms cleanly, with tests that prove correctness.

<context>
[ALGORITHM — e.g. "Dijkstra's shortest path", "merge sort", "Luhn check"]
[LANGUAGE AND VERSION — e.g. "Python 3.12", "TypeScript 5 / Node 20"]
[HOW IT WILL BE USED — e.g. "finding cheapest delivery routes between 40 depots, called a few times a day"]
[INPUT SHAPE — e.g. "adjacency list as dict[str, list[tuple[str, float]]]"]
[CONSTRAINTS — e.g. "standard library only", "must handle 10k nodes"]
</context>

Before coding, state the algorithm's contract: inputs, outputs, time and space complexity, and the 3-4 edge cases most likely to bite for MY stated use (e.g. unreachable nodes, duplicate edges, empty input).

<task>
1. Implement the algorithm idiomatically for [LANGUAGE AND VERSION]: typed where the language supports it, clear names, a 3-line docstring or comment explaining the approach, no dead code.
2. Match my stated input shape exactly; validate inputs and fail with clear messages rather than returning wrong answers.
3. Write tests in the language's mainstream test framework covering: one worked normal case (expected answer computed by hand and shown), each edge case from your pre-work, and one property or stress test sized to my constraints.
4. Note the complexity actually achieved, and any place a simpler-but-slower choice was made deliberately.
5. If my use case would honestly be better served by a library or a different algorithm, say so in two lines at the end — after still delivering what I asked for.
</task>

<output_format>
One code block for the implementation, one for the tests, then the exact command to run them and the notes. No prose between code blocks beyond one-line captions.
</output_format>

Rules:
- Code must be complete and runnable as pasted — no placeholder functions, no "rest of implementation" elisions.
- If the algorithm name is ambiguous (several variants), ask which variant before writing code.
- Use only details provided; unknown constraints become explicit assumptions listed at the top, maximum 3.

Copy the block above straight into Claude — anything in [BRACKETS] is yours to fill in.