When Some Links Cost More

Last timeFollowing One Path to the End

Weights break the ring walk immediately, and the repair is to serve the waiting line in order of cheapest known cost, which is one substitution and a proof.

The ring walk gives the wrong answer

Three towns. There is a road from the first to the third that takes two hours.

There is also a road from the first to the second taking ten minutes, and one

from the second to the third taking fifteen. The fewest links route is the

direct one, with a single link. The cheapest route is the other one, with two.

The ring walk will report the direct road, because it meets the third town at

distance one and never looks again. It is not malfunctioning; it is answering

the question it was built for, which is how few links, and that question has

stopped being the one anybody is asking.

FIG 1Two questions, two different answers

	links used	total cost in minutes	found by the ring walk
direct road	1	120	1
through the second town	2	25	0

The ring walk finds the first row because it has fewer links. The marked cell is the answer anybody actually wanted. Once the links carry different costs, the two columns disagree, and no amount of care with the ring walk will fix it, because the ring walk never looks at the costs at all.

Serving the line by cost

The repair is one substitution. Keep a best known cost for every point,

starting at zero for the start and at infinity for everything else. Instead of

taking whichever point joined the line first, take whichever point in the line

has the smallest best known cost. Look at its neighbours, and for each one,

check whether going through this point is cheaper than the best route known so

far. If it is, record the lower cost and put the neighbour in the line.

Everything else is the ring walk. The waiting line is the only thing that

changed, and the structure that serves it is the one from the ordering course

that promises its smallest item and nothing else, which is precisely the

promise needed here.

FIG 2Cheapest first, from a, with costs on the links

step	step	cheapest in the line	its cost	improved from it	best known costs
1	1	a	0	b to 4, c to 1	b 4, c 1
2	2	c	1	b to 3, d to 7	b 3, d 7
3	3	b	3	d stays 7	d 7
4	4	d	7	e to 9	e 9
5	5	e	9	nothing left	all settled

5 steps

Notice step two. The route to b was already known at a cost of four, and going through c brings it down to three, so the cheaper figure replaces it. That improvement is the part the ring walk has no equivalent of, and it is why a point can be put in the line more than once before it is finally settled.

Why settling a point is safe

The method commits. When a point comes out of the line as the cheapest one, it

is declared settled and never improved again. That is a strong claim and it

needs an argument.

Suppose the cheapest point in the line is $v$ , at cost $c$ . Could some route

discovered later reach $v$ more cheaply? Any such route has to pass through

some point that is still in the line, because the route has to leave the

settled region at some point, and the first point it reaches outside is in the

line. Call that point $u$ . Since $v$ was the cheapest in the line, $u$ costs

at least $c$ . The route then continues from $u$ to $v$ along links, and if no

link can reduce a cost, the total is at least $c$ . So nothing cheaper exists.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents