The value of being somewhere is the cost of the next step plus the value of where that step leads. Write that down at every node, fill it in from the last stage back, and a routing problem falls out in one pass. The formula is the easy half. The half this lesson is built on is what the table does not contain: it holds one number per node and no route at all, so the routes have to be reconstructed afterwards — and when two continuations are worth the same, there is more than one of them.
Core ideas
Three ideas, and the formula is only the first of them. The other two are about what the table is and what it costs.
What the recursion writes at each node is one quantity: the best total from there to the finish. It does not contain a path and cannot be asked for one. The routes are recovered at the end by walking the argmins forward from the start, and a node may have several argmins, so what comes back is a set of routes rather than a route. Reading the value as though it were a plan is what makes ties invisible.
f(v) is defined in terms of f(w) for the nodes v can reach, so it can only be written once those are settled. That is the whole reason the last stage comes first: its value is zero by definition, and every other value is built on values already final. A forward pass would need the answer before it could compute it, which is why the forward object in this lesson is an enumeration and not a second method.
Walking every path prices each path separately, and paths multiply as stages are added. The recursion prices each node once, and nodes add. On the network in the lab the two counts are 4 paths against 6 node values, which is no saving at all — and that is deliberate, because at this size you can check the recursion against the thing it replaces by eye. The saving is a shape, not a number.
The material
The definition, the order it forces, and then the instance whose answer is three routes rather than one.
A staged network is a list of stages, each holding some nodes, together with arcs that only ever run forward: an arc may join a node in one stage to a node in any later stage, never to one in the same stage or an earlier one. Each arc carries a cost.
The value function f gives each node the cheapest total from that node to the finish: f(w) = 0 for every node in the last stage, and f(v) = min over arcs out of v of c(v,w) + f(w) otherwise. An argmin at v is an arc attaining that minimum; there may be more than one.
The lab takes the stages as names separated by semicolons and the arcs one clause each, tail then > then head then cost. An arc that runs backwards or sideways is refused with the two stage numbers named, because that is a modelling error rather than a typing one: a network with a cycle in it has no last stage to start from and the recursion has nowhere to bottom out.
Read the last two lines again. f(A) is 8 and there are two ways to attain it, and f(B) is 8 with two ways to attain that. Following the argmins forward from A therefore produces three routes and not one: A B D F, A B E F and A C D F. The lab prices each of them again from the arcs before printing it, and all three come to 8.
This network has four paths in total. Walked forwards and priced independently they come to 8, 8, 8 and 10, so the best is 8 and exactly three paths attain it. That agrees with the recursion, which is the point: the lab runs both and prints both, and shows nothing as an answer when they disagree. The enumeration is an oracle, not an alternative algorithm — it is exponential on purpose, and offering it as a way to solve these problems would undo the lesson.
Change A>B from 0 to 2 and nothing else. Every value in the table is the same except f(A), which becomes min(2 + 8, 4 + 4) = 8 — still 8, but now attained only through C. The tie at B is still there, f(B) is still 8 with D and E both attaining it, and the four paths now cost 10, 10, 8 and 10.
So the answer is the same number and one route instead of three, and the tie that remains is on no optimal route at all. A recursion that dropped ties would give identical output on both networks. That is worth sitting with: the two cases are one arc cost apart, and nothing in the value 8 distinguishes them.
Add A>E 3 to the original network. The recursion needs no adjustment at all: f(E) is already settled when f(A) is written, because E lives in a later stage, and the new candidate is 3 + 4 = 7. That beats 8, so f(A) becomes 7 and the single optimal route is A E F. Walking all five paths forwards agrees. What makes this work is not a special case in the code but the ordering: a value is written only once everything it depends on is final, and a forward jump does not disturb that.
In a routing problem the stages are given: they are the columns of the map. In most of the problems on this course they are not. A stage is whatever index makes the arcs run one way — an activity, a time period, a candidate, a number of periods left — and choosing it is choosing the model.
That is why this lesson comes first and why it is the easiest one here. Everything about the recursion is visible because the hard half has been done for you. The rest of the course does the hard half.
One last property, easy to miss because it looks like an implementation detail: a value is written once and never revised. If you find yourself wanting to go back and improve f at a node already filled in, either the ordering is wrong or the state is — and the second of those is the subject of everything that follows.
Interactive
Every value the recursion writes, beside every path it stands for
Method
Five steps, and the last two are the ones people skip. Doing them in this order means you never revise a value.
Stage numbers on the tail and the head, and the head's must be larger. If any arc fails this there is no last stage to start from and the recursion has no base case. The lab refuses such an arc by name rather than drawing it.
One column at a time, right to left. Within a column the order does not matter, because nothing in a stage depends on anything else in it.
c(v,w) + f(w) for each arc, then the minimum — and then a second pass for any other arc attaining it. Writing down only the first is where the ties go.
From the start, branching wherever a node has more than one argmin. This is the step that turns a table of numbers into something you can act on, and it is the step at which a reader discovers the answer is a set.
Add the arc costs along it and check the total against the value at the start. The recursion and the reconstruction are two pieces of arithmetic, and only the second one produces the thing you were actually asked for.
Both tables below are filled from F back. Only the cost of A>B differs, and only the last line of each table does.
The two columns agree on the answer and disagree on how many answers there are. Nothing in the number 8 carries that difference, and neither does the drawing unless the ties are drawn — which is why the lab colours a tied arc differently from a chosen one and reports the tied nodes as a field of their own.
For a rehearsal, put A>B back to 0 and change D>F from 1 to 2 instead. Work out by hand what happens to f(D), f(B), f(C) and f(A), and how many optimal routes survive, before you let the lab tell you. The answer is still 8 and there is now exactly one route; the third rehearsal below is the one that goes the other way.
The harder rehearsal: add an arc from A straight to F and give it a cost of 9, then 8, then 7. At 9 nothing changes; at 8 the set of optimal routes grows by one; at 7 every other route stops being optimal and the answer becomes a single arc. Three regimes, one number, and the recursion never needed to be told that the arc skipped two stages.
You should be able to write f at each node from the last stage back, record every argmin rather than one, reconstruct the routes by walking forward, price each of them again from the arcs, and explain why changing a single arc cost can change the number of optimal routes without changing the answer.
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.