Shortest Paths on a DAG
In short: on a directed acyclic graph (DAG) — where legs only ever point "forward", with no way back to a stop already visited — one sweep in topological order finds every cheapest cost, even with negative edges, in O(V + E). Process stops in an order where every leg into a stop comes from an earlier stop, and by the time you reach a stop every leg that could lower its cost has already run. No heap, no settling order to argue about: the order itself is the proof.
Meridian has a model of the city. This section routes things through it and builds the router, starting with the night timetable. After midnight, shuttles run between depots on fixed times, and time only moves forward, so no chain of shuttles can bring you back to where you started. The timetable is a directed acyclic graph, a DAG.
The twist: some legs carry return freight that Meridian is paid for, so on the books they have a negative cost, a credit. You saw a negative edge fool Dijkstra in the graphs section. On a DAG you don't need Dijkstra at all: one sweep through the stops, in the right order, finds every cheapest cost, credits included, in O(V + E).
Where Dijkstra goes wrong
Dijkstra settles the cheapest unsettled stop and never looks at it again. The promise behind that is "nothing found later can be cheaper", and a credit breaks it. Here the mill is settled at 2, but the route through the quay reaches it for 5 − 4 = 1:
import heapq
legs = {"depot": [("mill", 2), ("quay", 5)], "quay": [("mill", -4)],
"mill": [("harbour", 3)], "harbour": []}
settled = set()
best = {"depot": 0}
heap = [(0, "depot")]
while heap:
cost, stop = heapq.heappop(heap)
if stop in settled:
continue
settled.add(stop)
for nxt, step in legs[stop]:
if nxt not in settled and cost + step < best.get(nxt, float("inf")):
best[nxt] = cost + step
heapq.heappush(heap, (cost + step, nxt))
print(best["harbour"])Dijkstra guessed which stop was final from costs. With no cycles there is a better source of truth: the order of the stops.
The order is the argument
Put the stops in topological order, so that every leg runs from an earlier stop to a later one. You built this order in the graph structure section with Kahn's algorithm: count the legs into each stop, emit a stop when its count reaches zero, and lower the counts of the stops it points at.
Now look at any stop in that order. Every leg into it comes from a stop earlier in the order. So if you process the stops in order and relax every leg out of each one, then by the time you reach a stop, every leg that could lower its cost has already been relaxed. Its cost is final. It doesn't matter whether any of those legs were credits. No later discovery can change it, because nothing later points back.
That is the whole algorithm:
- Find a topological order.
- Set the start to 0 and every other stop to unknown.
- Walk the order. For each stop with a known cost, relax each leg out of it.
Watch it on the night network. The stops are drawn in rows by their position in the order, and each badge is the cheapest cost known so far. A settled badge never changes again:
In topological order, every leg into a stop is relaxed before the stop is reached, so each badge settles once and never moves again, credits and all.
The depot comes first in the order and costs nothing to reach. 6 nodes, 8 edges, directed. At depot. Settled: depot. depot: 0.
order: depot, quay, mill, yard, market, harbour
The mill was processed after the quay even though it is cheaper to reach. The sweep picks what to process next by order alone, never by cost.
The sweep in code
The order comes from Kahn's algorithm, and the sweep is a single loop over it:
Your order may differ from the picture's. Any valid order works; the argument only needed "every leg points forward".
How much work is that? Kahn's algorithm looks at every leg once, and so does the sweep.
out = {
"depot": [("quay", 5), ("mill", 2)], "quay": [("yard", -4)],
"mill": [("yard", 3), ("market", 4)], "yard": [("market", 1), ("harbour", 6)],
"market": [("harbour", 2)], "harbour": [],
}
order = ["depot", "quay", "mill", "yard", "market", "harbour"]
best, checks = {"depot": 0}, 0
for stop in order:
for nxt, cost in out[stop]:
checks += 1
if best[stop] + cost < best.get(nxt, float("inf")):
best[nxt] = best[stop] + cost
print(checks)The order, the waiting counts and the best costs are each one entry per stop
or leg, so the sweep also costs O(V + E) space — no heap, and nothing extra
to store beyond the graph itself.
Step through two stops of it by hand. Watch the yard's cost get offered twice and keep the smaller one:
Order is not optional
The sweep's correctness comes entirely from the order. Relax the same legs in the order they happen to be listed, and a stop can pass on its cost before that cost is final:
The cheapest route is depot → quay → yard → harbour, costing 5 − 4 + 1 = 2, but this prints 4. Make the relaxation follow the topological order.
Your sweep, drawn
Here is the whole thing, Kahn's order then the sweep, drawing each relaxation.
Try giving the mill → yard leg a credit of its own, say -2, and see which route
the harbour takes. Or add a leg that closes a loop, like ["harbour", "depot", 1],
and watch what the order does to the stops on it.
Your sweep. A stop is only processed once everything pointing at it is done, so its badge is final when its turn comes.
If you added the loop, the stops on it never reach an in-degree of zero, and they never get processed at all. The sweep is only defined on a DAG, and Kahn's algorithm is also how you find out whether you have one.
It's dynamic programming wearing a map
Write down what the cheapest cost to a stop is:
That's a recurrence, exactly like the ones in the dynamic programming lessons. Each
subproblem, "cheapest cost to u", is reused by every leg leaving u. The DAG is
the dependency graph of the subproblems, and the topological order is the order you
fill the table in. Written top-down with a cache, it is the same algorithm:
The recursion finds its own order; the sweep writes it down in advance. Any problem whose states form a DAG is a shortest-path problem in disguise.
Nothing here depends on the sign of a cost, so swapping min for max gives the
longest route through a DAG, a problem with no known fast algorithm on general
graphs.
Why brute force isn't an option
Suppose each hour has 4 stops, each with a shuttle to every stop in the next hour. There are 4 to the power of the number of hours routes to price, but the sweep relaxes just 16 legs per hour:
| hours | routes to price | legs the sweep relaxes |
|---|---|---|
| 5 | 1,024 | 80 |
| 10 | 1,048,576 | 160 |
| 12 | 16,777,216 | 192 |
A night timetable runs about ten hours, so brute force is out the moment the timetable is real.
Interview-style: the toll pass
Here's a problem in the shape interviewers like, worded for Meridian. A van crossing the night network carries a single toll pass. On one leg of its route it may use the pass to make that leg free. What is the cheapest possible run from the depot to the harbour?
The tempting answer is to find the cheapest route and waive its dearest leg. That fails when a slightly dearer route hides one huge leg. The reliable approach is to make the pass part of the state: every stop becomes two, pass held and pass spent. A held state can pay a leg (stay held) or waive it (become spent). The state graph is still a DAG, still in the same order, so one sweep solves it. The boss exercise asks you to build it.
What it costs
| Algorithm | Time | Works when |
|---|---|---|
| DAG sweep (Kahn + relax) | O(V + E) | no cycles; any costs, including credits |
| Dijkstra with a heap | O((V + E) log V) | cycles allowed; costs never negative |
| Bellman-Ford (next lesson) | O(V × E) | cycles and credits; detects money-making loops |
❓ Cross-question — "Roads are two-way, so where do DAGs actually show up?" Wherever one quantity only moves one way: time in a timetable, stages in a pipeline, days in a plan. Turn "stop" into "stop at a moment" and a cyclic map becomes an acyclic timetable, which is what the capstone exercise does.
Quick practice
out = {"a": [("b", 1), ("c", 4)], "b": [("c", -2)], "c": [("d", 3)], "d": []}
order = ["a", "b", "c", "d"]
best = {"a": 0}
for stop in order:
if stop not in best:
continue
for nxt, cost in out[stop]:
if best[stop] + cost < best.get(nxt, float("inf")):
best[nxt] = best[stop] + cost
print(best["d"])KeyErrorc can't be reached from a, so the sweep should just skip it, but reading best["c"] crashes. Add the missing check.
🎯 Your turn
Write dag_route(legs, start, goal). legs is a directed, acyclic edge list of
[from, to, cost], and costs may be negative. Return the cheapest route as
{"cost": total, "path": stops}, or {"cost": None, "path": []} if goal can't
be reached:
dag_route([["depot", "quay", 5], ["depot", "mill", 2], ["quay", "yard", -4], ["mill", "yard", 3], ["yard", "harbour", 1]], "depot", "harbour")→{"cost": 2, "path": ["depot", "quay", "yard", "harbour"]}- the same legs from
"mill"to"mill"→{"cost": 0, "path": ["mill"]}
Hint: Kahn's algorithm for the order, one sweep with best and parent, then
walk parent back from the goal.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's router is built. ✅