Cheapest route with nonnegative costs
“A delivery planner knows directed road costs. The route with the fewest roads can be expensive, so return minimum total cost and the route itself. All supplied costs are nonnegative. When is a tentative route safe to call final?”
Write this:
def weighted_shortest_path(graph, source, target):
... # Return a cheapest path; raise OverflowError on an unrepresentable sum.
Constructed practice question. Prerequisites: graphs and heaps. A min-heap retrieves the smallest tentative cost; relaxing an edge means replacing a known cost when that edge improves it.
| Contract | Required behavior |
|---|---|
| Input | Mapping of every vertex to (neighbor,weight) pairs; source and target |
| Output | (minimum_cost, endpoint-inclusive_path); any tied shortest path |
| Boundaries | Unreachable returns (math.inf, []); source=target returns (0,[source]) |
| Failure | Missing vertices, bool or negative/nonfinite weights raise ValueError; an evaluated sum outside float range raises OverflowError |
| Scope | Directed, static graph; nonnegative int/float weights; integer-only sums stay exact |
Optional refresher · the underlying tool
When edges have nonnegative weights, a FIFO queue is insufficient: the earliest discovered route might cost more. A min-heap orders tentative distances:
from heapq import heappush, heappop
heap = [(0, "A")]
heappush(heap, (10, "B"))
heappush(heap, (1, "C"))
print(heappop(heap)) # (0, 'A'); then C before B
If A→B costs 10, A→C costs 1 and C→B costs 1, the best cost to B is 2. Skip stale entries when a cheaper route has already been recorded.
A design choice worth saying aloud
best_cost holds the cheapest known route; heap entries are candidates, not committed answers. On pop, skip a candidate whose cost differs from the best recorded cost, since a better path may have arrived later. This proof uses nonnegative edges; with negative costs, the greedy finalization argument fails.
What the interviewer expects
The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.
Done means: (minimum_cost, endpoint-inclusive_path); any tied shortest path.
Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.
Test-case scenarios to settle before coding
01 · Relaxation
- Input / starting state
- A→B 8, A→C 1, C→B 2
- Expected result
(3,[A,C,B])
What it is testing: First discovery is not final.
02 · Same vertex
- Input / starting state
- source equals target
- Expected result
(0,[source])
What it is testing: The empty edge path is valid.
03 · Unreachable
- Input / starting state
- target in a disconnected component
- Expected result
(inf,[])
What it is testing: Absence has an explicit pair result.
04 · Zero-cost cycle
- Input / starting state
- cycle edges cost zero
- Expected result
- terminates with an optimal simple witness
What it is testing: Stale heap work must not loop.
05 · Huge integers
- Input / starting state
- weights beyond float precision
- Expected result
- exact integer total
What it is testing: Do not coerce costs to float.
06 · Invalid anywhere
- Input / starting state
- negative/nonfinite edge in disconnected component
- Expected result
ValueError
What it is testing: Whole-graph validation is not traversal-dependent.
For each case, show which branch or state change produces that result.
For A→B:8, A→C:1, and C→B:2, return (3,[A,C,B]), even though B was
discovered directly first. A disconnected target returns infinity and no path.
Integer-only routes retain arbitrary precision. Float or mixed routes use Python
float arithmetic: near ties may round, and any evaluated relaxation whose
sum is unrepresentable raises OverflowError, even if another route exists.
Infinity is reserved for unreachable results, not reachable costs. Inputs are
not mutated. Use exact integer units when the domain requires exact costs.
| Numeric trace | Result |
|---|---|
1e308 + 1e308 along a reachable route |
OverflowError, not “unreachable” |
10**400 + 0.5 |
OverflowError on the mixed addition |
10**400 + 10**400 using integers only |
Exact 2 * 10**400 |
| Finite graph with disconnected target | (math.inf, []) |
Implement before opening the solution. Explain why returning when B is first inserted is wrong, and predict what happens to B's old heap entry.
Solution, stale entries, and changed assumptions
BFS optimizes edge count, so it chooses the cost-eight direct edge here. A correct baseline repeatedly scans all unsettled vertices for minimum tentative cost, taking O(V² + E). Replacing that scan with a min-heap makes sparse graphs cheaper.
Start source at zero. Pop the minimum; discard it if its saved cost differs from the current best distance. Otherwise relax outgoing edges, updating distance and parent and pushing a fresh heap entry for each strict improvement. The heap need not support decrease-key: obsolete entries remain until popped. A sequence number breaks ties so vertex IDs need only be hashable, not mutually comparable.
when a nonstale minimum is removed, its distance is final. Any cheaper alternative would cross from an already finalized vertex to an unfinished one whose tentative distance is no greater; nonnegative edges prevent later suffixes from making that alternative cheaper. Therefore target early return is safe on valid removal, never on first discovery.
| Pop | Best distance to B | Heap after relaxation |
|---|---|---|
| A at 0 | 8 | C at 1; B at 8 |
| C at 1 | 3 | B at 3; B at 8 |
| B at 3 | 3 final | Old B at 8 is stale if search continues |
With lazy duplicates, heap size is O(E), not necessarily O(V). Validation is O(V + E); total time is O(V + E log(E + 1)) and auxiliary space O(V + E), excluding the O(P) returned path. This bound also covers parallel edges. For a simple graph, log E = O(log V). Arithmetic and hash lookups are treated as constant-time.
Follow-up 1 — allow a negative discount edge. Predict the result if A→B costs 2, A→C costs 5, and C→B costs -10. Finalizing B at 2 is wrong: the true cost is -5. Reject such inputs or choose an algorithm such as Bellman–Ford with explicit negative-cycle semantics; removing validation does not extend Dijkstra's proof.
Follow-up 2 — return distances to every vertex. Remove target early return and process all reachable entries, skipping stale ones. Keep infinity for unreachable vertices. Repeated requests on a changing graph need a versioned snapshot; a cached route may remain a valid path while no longer being cheapest.
Senior depth includes zero-cost cycles, stale entries, exact heap-space bounds, and an independent relaxation oracle. Lead depth asks who owns cost freshness and what the caller should do if a route expires during use.
Reference: solution.py (download file, source below); tests compare seeded graphs with repeated relaxation, and cover zero cycles, incomparable IDs, invalid edges, and no route.
"""Dijkstra with a lazy heap, stale-entry rejection, and path reconstruction."""
import heapq
import math
from itertools import count
def weighted_shortest_path(graph, source, target):
"""Return a cheapest path; raise OverflowError on an unrepresentable sum.
Integer-only routes retain arbitrary precision. Float routes use Python
float precision; every evaluated relaxation must have a finite result.
"""
if source not in graph or target not in graph:
raise ValueError("missing endpoint")
for edges in graph.values():
for neighbor, weight in edges:
if neighbor not in graph or type(weight) not in (int, float):
raise ValueError("invalid edge")
if (isinstance(weight, float) and not math.isfinite(weight)) or weight < 0:
raise ValueError("finite nonnegative weights required")
distance = {source: 0}
root_marker = object()
parent = {source: root_marker}
sequence = count()
heap = [(0, next(sequence), source)]
while heap:
cost, _, vertex = heapq.heappop(heap)
if cost != distance[vertex]:
continue
if vertex == target:
path = [vertex]
while parent[path[-1]] is not root_marker:
path.append(parent[path[-1]])
return cost, path[::-1]
for neighbor, weight in graph[vertex]:
try:
new_cost = cost + weight
except OverflowError as exc:
raise OverflowError("path cost is not representable") from exc
if isinstance(new_cost, float) and not math.isfinite(new_cost):
raise OverflowError("path cost is not representable")
if new_cost < distance.get(neighbor, math.inf):
distance[neighbor] = new_cost
parent[neighbor] = vertex
heapq.heappush(heap, (new_cost, next(sequence), neighbor))
return math.inf, []
python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/25-weighted-shortest-path -p 'test_*.py'