Capstone: Meridian's Router
In short: no single shortest-path algorithm is right for every network — each one trades correctness for speed differently. A router should classify the network it's handed (no cycles? any negative costs? all costs equal?) and run the cheapest algorithm that is still correct, checking from cheapest to most expensive so a fast, safe answer is never skipped in favour of a slow, safe one. Kahn's algorithm answers "any cycles?" for free, as a side effect of trying to find a topological order.
You now have five ways to find a cheapest route, and each is the right answer to a different question:
| The network | The algorithm | Cost | Lesson |
|---|---|---|---|
| no cycles (time only moves forward) | topological sweep | O(V + E) | 1 |
| cycles and negative costs | Bellman-Ford, with a loop check | O(V × E) | 2 |
| every pair, small and dense | Floyd–Warshall | O(V³) | 3 |
| one query, known goal, a map | A* | far fewer expansions | 4 |
| one long query, known goal | search from both ends | about 2·b^(d/2) | 5 |
and the two you started with: BFS when every road costs the same, and Dijkstra when costs are non-negative. That's the whole shortest-path toolkit, and the skill that remains is choosing. Pick too weak a tool and you get a wrong answer (Dijkstra on rebates). Pick too strong a tool and you're slow (Bellman-Ford on a street map).
This capstone builds the piece that chooses: route_query(roads, start, goal), the
single entry point to Meridian's router. It looks at the network it has been handed,
picks the cheapest algorithm that is still correct for it, runs it, and reports
which one it used.
The decision, in order
The checks run from cheapest to most expensive algorithm:
- No cycles at all? Use the topological sweep. It's the fastest correct algorithm there is, and credits don't bother it, so this check comes first even if some costs are negative.
- Any negative cost? Then (with cycles present) only Bellman-Ford is correct, and it must check for money-making loops.
- Every cost the same? BFS order is cheapest order, and the cost is hops × that weight.
- Otherwise costs are non-negative and mixed: Dijkstra.
Kahn's algorithm answers the first question for free: if it emits every stop, there is no cycle. Watch the router classify the night timetable, then the same network with one return road added:
If Kahn's algorithm emits every stop there is no cycle and the sweep is safe; one return road leaves every stop waiting, and the router must fall back.
Each badge counts the roads into a stop. Only the depot waits on nothing. 4 nodes, 4 edges, directed. Frontier: depot. depot: 0, mill: 1, quay: 1, harbour: 2.
The set of costs answers the other two:
The order of the checks is a policy, and it matters:
roads = [["depot", "mill", -1], ["mill", "quay", -1], ["quay", "harbour", -1]]
out = {"depot": ["mill"], "mill": ["quay"], "quay": ["harbour"], "harbour": []}
waiting = {"depot": 0, "mill": 1, "quay": 1, "harbour": 1}
ready, emitted = ["depot"], 0
while ready:
n = ready.pop()
emitted += 1
for nxt in out[n]:
waiting[nxt] -= 1
if waiting[nxt] == 0:
ready.append(nxt)
costs = {c for _, _, c in roads}
if emitted == len(out):
print("dag")
elif min(costs) < 0:
print("bellman-ford")
else:
print("bfs" if len(costs) == 1 else "dijkstra")Reversing the first two checks would still give correct answers, only slower. Other reorderings are not safe: checking "all costs equal" before "any negative" would send a network where every road costs −1 to BFS, which would happily report a cost when the true answer is "no cheapest route exists".
roads = [["depot", "mill", -1], ["mill", "depot", -1], ["mill", "harbour", -1]]
costs = {c for _, _, c in roads}
if len(costs) == 1:
print("bfs")
elif min(costs) < 0:
print("bellman-ford")Step through the set logic that the last two checks rest on:
One shared ending
Whichever algorithm runs, have it fill the same two dicts, best and parent.
Then "not reachable" (goal missing from best) and "rebuild the path" (walk
parent back) are one piece of code at the end instead of four. Bellman-Ford is the
one branch that can return early: if the goal is downstream of a money-making loop,
the answer is "loop", and there is no path to rebuild.
The BFS branch has one trap. BFS counts roads, and the router promises cost:
The harbour is three roads away and every road costs 2, so the cheapest cost is 6, but this prints 3. Make the BFS branch add the shared weight.
Your router, drawn
Here is a cut-down router: it classifies the network, then runs the chosen
algorithm and draws every improvement, and at the end it reports how many relaxation
checks it made. As given, the roads are one-way and loop-free, so it picks the
sweep. Add ["harbour", "depot", 4] to create a loop and it switches to Dijkstra;
then change one cost to negative and watch it fall back to Bellman-Ford, and
compare the counts.
Your router. The same query costs a different amount of work depending on which algorithm the network allows.
On the loop-free network the sweep checks each of the 8 roads exactly once. Bellman-Ford on the same roads would make up to 8 × 5 = 40. The router's whole value is in not paying that price when it doesn't have to.
Classifying the network is one Kahn's-algorithm pass, O(V + E) time and space, on top of whichever algorithm it then picks — negligible next to the search itself, and worth it to never run the wrong one.
When is Bellman-Ford affordable?
Sometimes it is the only correct choice, and then the question is whether it fits the time budget. At around a hundred million relaxations a second, a 1-millisecond answer allows about 100,000 of them. A tariff network with V junctions and about 3V roads needs up to 3V × V relaxations: 7,500 at 50 junctions, 99,372 at 182 and 100,467 at 183. So 182 junctions is the largest network that fits. The cost grows with V squared, so doubling the network quadruples the work. Past that size a router either precomputes (Johnson's potentials, overnight) or restricts negative costs to places where the sweep can handle them.
Interview-style: the backup route
When an incident blocks the best route, drivers want the next-best ready. Given two-way roads, what does the cheapest route cost that is strictly dearer than the best one? Routes may revisit junctions.
The trick is to let Dijkstra settle each junction twice: once at its cheapest cost, and once at the cheapest cost strictly above that. A heap entry that would be a third arrival, or a repeat of a known cost, is thrown away. Any second-best route to the goal is built from first- or second-best routes to the junction before it, so two settlements are enough. The boss exercise builds it, and the capstone exercise asks the planner's version: which single road closure hurts a key route the most.
What you've built
| Piece | Function | What it does |
|---|---|---|
| Timetable | dag_route() |
cheapest run through an acyclic timetable, credits and all |
| Tariffs | tariff_route() |
cheapest route under rebates, or an honest "loop" |
| Depot matrix | depot_matrix() |
every depot-to-depot cost, overnight |
| Live map | astar_route() |
aimed search for one route on the street grid |
| Cross-city | meet_in_middle() |
two searches meeting in the middle |
| Router | route_query() |
picks the right one of them for the network in hand |
❓ Cross-question — "Real routers don't re-classify the network on every query, do they?" No. The network changes slowly, so they classify once, and precompute what the class allows: potentials for rebates, landmark tables for A*, a depot matrix for pricing. Queries then pay only for the search. Your
route_querydoes the classification per call to keep the whole idea in one place.
Quick practice
def classify(roads):
out, waiting = {}, {}
for a, b, _ in roads:
out.setdefault(a, []).append(b)
out.setdefault(b, [])
waiting[b] = waiting.get(b, 0) + 1
ready = [n for n in out if waiting.get(n, 0) == 0]
emitted = 0
while ready:
n = ready.pop()
emitted += 1
for nxt in out[n]:
waiting[nxt] -= 1
if waiting[nxt] == 0:
ready.append(nxt)
costs = {c for _, _, c in roads}
if emitted == len(out):
return "dag"
if min(costs) < 0:
return "bellman-ford"
return "bfs" if len(costs) == 1 else "dijkstra"
print(classify([["a", "b", 2], ["b", "c", 2], ["c", "a", 2]]))p, q and r form a loop that pays on every lap, so this network needs Bellman-Ford's loop check, but the router picks "bfs" instead. Reorder the two checks.
🎯 Your turn
Write route_query(roads, start, goal). Classify the directed network ("dag",
then "bellman-ford", then "bfs", then "dijkstra"), run the matching
algorithm, and return {"method": ..., "cost": ..., "path": [...]}, with cost
None if the goal is unreachable and "loop" if a money-making loop feeds it:
route_query([["depot", "mill", 2], ["mill", "harbour", 3], ["depot", "harbour", 9]], "depot", "harbour")→{"method": "dag", "cost": 5, "path": ["depot", "mill", "harbour"]}
Hint: reuse your code from lessons 1 and 2, and keep one best/parent pair
for every branch so the ending is shared.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = Meridian's router is built. ✅