On an acyclic digraph the arcs can be put in an order where every tail is settled before its head is ever relaxed, so one relaxation per arc is enough — no rounds, no heap, and negative weights make no difference. Reverse the comparison and the same pass returns the longest path instead, which on a general graph is a problem no algorithm on this course solves. The difference is that a DAG has no cycle to go round for profit.
Core ideas
The hard idea is why one pass suffices. Longest paths and slack are both that same pass with a sign or a direction changed.
Process the vertices in topological order. When v is reached, every arc into v came from a vertex earlier in the order, and every earlier vertex has already had all its outgoing arcs relaxed. So d[v] is final the moment v is reached, and each arc is relaxed exactly once. On the lab's opening project the pass performs 7 relaxations on 7 arcs, and the rounds method on the same graph agrees with the answer.
Reverse the comparison in the relaxation step and the pass maximises instead. That would be nonsense on a general graph — a positive cycle could be walked forever — but a DAG has no cycle at all, so the longest path is finite and the same argument goes through unchanged. On the opening project the shortest route to the end is 6 and the longest is 10.
The latest a vertex may be scheduled without delaying the end is computed backwards: seed only the far end at its own earliest time, and take the minimum over successors of their latest minus the arc weight. Slack is latest minus earliest. Seeding every vertex at its own earliest time instead gives zero slack everywhere, which looks plausible and is wrong; the lab computes it the right way and reports the vector.
The material
Why a single pass suffices, the sign flip, the backward pass and slack, and what happens when there is no order.
On an acyclic digraph processed in topological order, d[v] equals the shortest distance from the source at the moment v is visited, and each arc is relaxed exactly once.
By induction along the order. The source's label is 0 and correct. Let v be the next vertex, and let s, ..., u, v be a shortest path to it.
Every arc of that path goes forwards in the topological order, so u precedes v and was visited earlier. By hypothesis d[u] was correct when u was visited, and the arc from u to v was relaxed then, giving d[v] ≤ d[u] + w, which is the true distance. The upper-bound invariant says it is no smaller.
Each arc is relaxed when its tail is visited, and each vertex is visited once, so the arc count is exact.
□
Nothing in that argument mentions the sign of a weight. A negative arc changes which number is smaller and changes nothing about the order in which vertices are visited, which is why this is the one shortest-path method on the course that handles negative weights at no extra cost at all.
The lab opens on 1>2 3, 1>3 2, 2>4 4, 3>4 1, 4>5 2, 3>5 7, 5>6 1. A topological order is 1, 3, 2, 4, 5, 6. The shortest pass gives 0, 3, 2, 3, 5, 6 in 7 relaxations, one per arc, by the route 1, 3, 4, 5, 6. The longest pass, on the same 7 relaxations, gives 0, 3, 2, 7, 9, 10 by the route 1, 3, 5, 6. Both are confirmed by the rounds method on the shortest reading.
Read the longest reading as a project: each arc is a task with a duration and each vertex is a milestone. The longest distance to a vertex is the earliest it can happen. The latest it may happen without delaying the end is computed the other way, and the difference is the slack — how much the corresponding task may slip for free.
Three details in that backward pass all produce something that looks like slack when they are wrong. It must be seeded ONLY at the far end, and at the far end's own extreme distance. Its extremum is the opposite of the forward pass's: under the longest reading the backward pass takes a minimum over successors. And the subtraction goes the arc's own way, latest of the head minus the weight. Get any of the three wrong and the answer is a vector of plausible non-negative numbers.
On the opening project every vertex has slack 0 under the longest reading, because every vertex lies on a critical path: the latest vector equals the earliest vector exactly. On the lab's wide preset 1>2 5, 2>3 5, 3>6 5, 1>4 7, 4>5 4, 5>6 3, 1>6 2 the longest distances are 0, 5, 10, 7, 11, 15 and the slack is 0, 0, 0, 1, 1, 0: the route through 4 and 5 finishes at 14 where the critical route finishes at 15, so those two milestones may each slip by one.
The shortest reading has a slack of its own and it means something different: on the opening project it is 0, 4, 0, 0, 0, 0, so vertex 2 is four longer than the cheapest route needs. Slack is never negative under either reading, which is a cheap check that the backward pass was done correctly.
On 1>2 2, 1>3 3, 3>2 -2, 2>4 1 the topological order is 1, 3, 2, 4 and the one pass gives 0, 1, 3, 2 in 4 relaxations. The rounds method agrees. The nearest-unfinished-first schedule gives 0, 1, 3, 3: it settled vertex 2 at label 2, relaxed the arc out of it from that label, and by the time vertex 2 improved to 1 it had already been declared finished. The lab prints all three.
The gap is one at vertex 4, which is small enough to be missed and large enough to be wrong. It is the clearest demonstration on this course that settling is an assumption rather than an optimisation: the topological schedule settles too, in the sense that d[v] is final when v is visited, but it settles in an order the arcs themselves justify.
On 1>2 3, 2>3 2, 3>1 1, 3>4 5 there is no topological order, and the lab returns no distances rather than numbers. That refusal is the right behaviour and it is worth seeing why the longest reading in particular cannot be rescued: negate every weight and the cycle 1, 2, 3 becomes a cycle of weight -6, so the rounds method reports it as a negative cycle. A longest walk on a graph with a cycle does not exist, and the trick that computes it on a DAG does not extend.
Measured against proved. On the opening project: 7 relaxations for the shortest reading and 7 for the longest, on 7 arcs, plus one topological sort. That is Θ(V + E) for that graph. The bound is Θ(V + E) on every acyclic graph, and the proof is that each arc is relaxed when its tail is visited and each vertex is visited once — so unlike the rounds method, the measurement here cannot vary with the arc order at all.
Interactive
One pass in topological order, negative weights allowed, and the sign flip that gives the critical path
Method
Order first, then one sweep. Everything else is the same sweep read differently.
The whole saving depends on every tail being visited before its head, and that is what the topological order guarantees and nothing else does. If the order does not exist, stop and say so: there is no repair, and the rounds method is the tool for that graph.
Sweeping the arcs by tail, in order, is what makes the arc count exactly E. Relaxing into each vertex from its predecessors is equally valid and needs the reversed arc list; mixing the two is how an arc gets relaxed twice or not at all.
Not the weights, not the order, not the initialisation. Negating the weights also works and is a useful way to see why it is legitimate, but it is two changes where one will do, and on a graph with a cycle it is the version that exposes why the trick fails.
Seed the far end at its own extreme distance and nothing else, take the opposite extremum over successors, and subtract each arc's weight from the head's value. Then check that no slack came out negative — that check costs nothing and catches all three of the ways this pass is usually written wrong.
The arcs are 1>2 3, 1>3 2, 2>4 4, 3>4 1, 4>5 2, 3>5 7, 5>6 1, and the topological order the lab produces is 1, 3, 2, 4, 5, 6.
Under the longest reading, vertex 4 goes to 7 when vertex 2 is visited and stays there when vertex 4 itself is visited, because the route through 2 is longer than the route through 3. Under the shortest reading the opposite happens. The two columns differ at exactly the vertices where the two routes differ, and nothing else about the pass changed.
Notice that the longest reading leaves no slack anywhere on this project. That is not the usual case; it means every milestone lies on some critical path, so any delay anywhere delays the end. The lab's wide preset is the contrasting shape, where two routes race and the slower one has a spare unit at each of its two interior vertices.
For a faded rehearsal, change 3>5 7 to 3>5 3 and predict both readings before running it. The supplied first move is this: the longest route to 5 was 1, 3, 5 at 2 + 7 = 9, and the competing route 1, 2, 4, 5 is 3 + 4 + 2 = 9 as well. Say which route becomes critical, what the longest distance to 6 becomes, and where slack now appears.
You should be able to compute a topological order, relax each arc exactly once in that order, flip the comparison for the longest path, run the backward pass seeded at the far end to get slack, and say precisely why the settling schedule is wrong on a DAG with a negative arc while this one is not.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.