Spreading Out One Ring at a Time

Last timeWriting a Graph Down

Visiting a graph in rings of increasing distance finds the fewest-link route to everything reachable, and the proof of that is one sentence about the order points are met in.

The order you meet things in

Start at one point. Visit everything one link away. Then everything two links

away that has not been seen. Then three. Keep going until nothing new appears.

That is the whole method, and it needs no arithmetic at all to carry out. The

machinery is a waiting line. Put the start in it. Repeatedly take the point at

the front, look at its neighbours, and put any neighbour not seen before at

the back. Because the line is served front to back, everything one link away

is taken out before anything two links away, which is taken out before

anything three links away. Nobody counts distances to make this happen. It is

a property of serving the line in the order it was joined.

FIG 1Spreading out from a, one ring at a time

step	step	taken from the front	its neighbours	newly added	the line now
1	1	a	b, c	b, c	b, c
2	2	b	a, d	d	c, d
3	3	c	a, d	nothing	d
4	4	d	b, c, e	e	e
5	5	e	d, f	f	f
6	6	f	e	nothing	empty, done

6 steps

The six point graph from the previous lesson. The first ring is b and c, the second is d, the third is e, the fourth is f. Notice step three: c offers d, which is already in the line, so nothing happens. That check is the whole of the bookkeeping, and the next section is about where exactly it has to go.

Why the first arrival is the shortest

Walking everything is easy. The reason this particular order matters is that

it answers a question, and the question is how few links away is each point.

The claim is that when a point is first reached, it is reached by a route with

the fewest possible links. The argument is short. Suppose a point $v$ is first

reached at distance $k$ , and suppose there were a better route of length

$j < k$ . That better route arrives at $v$ from some point $u$ at distance

$j - 1$ . But every point at distance $j - 1$ was taken out of the line before

any point at distance $k - 1$ , and when $u$ was taken out, all of its

neighbours were added, including $v$ . So $v$ would have been reached at

distance $j$ , not $k$ , which contradicts where we started.

FIG 2The distance of a point, built from its neighbours

: the fewest links from the start to the point v
: any point u with a link to v

The distance to a point is one more than the distance to the nearest point that links to it. The ring method computes this without ever evaluating the minimum, because it reaches v from the nearest such u first by construction.

So the method is not merely a tour that happens to be tidy. Recording, for

each point, how far it was when first reached, gives the shortest distance

from the start to every reachable point, all in one pass. Recording which

point it was reached from gives the route itself, read backwards.

That is a great deal of answer for one walk, and it is exactly and only

correct when every link counts the same. The fifth lesson is about what

happens when they do not.

The lesson stops here

4 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

Spreading Out One Ring at a Time

The order you meet things in

Why the first arrival is the shortest

4 more paragraphs to go

This is the reading half

Read alongside