Connecting Everything Cheaply

Last timeDoing Things in a Possible Order

Joining every point for the least total cost is the one problem in this course where taking the cheapest thing available at every step is provably right.

A different question entirely

Every question so far has been about travelling. This one is about building.

There are points, and a cost for each possible link, and the task is to choose

a set of links so that everything is joined to everything else, for the least

total cost. Laying cable between buildings, running pipe between tanks,

deciding which flights an airline must keep to serve all its cities, grouping

observations by linking the nearest pairs. The traveller does not appear

anywhere; nobody is going from one place to another. The question is which

links to pay for.

It is worth noticing immediately that the answer will not generally contain

the cheapest route between any particular pair. A structure that joins

everything at the least total cost may make two specific points very distant

indeed, and the lesson on travelling is answering a different question than

the lesson on building.

The count of links is not the question

Here is the first useful observation. Whatever set of links is chosen, if it

joins all $n$ points and contains no waste, it has exactly $n - 1$ links.

The reason is a count. Start with $n$ separate pieces. Each link added either

joins two pieces, reducing the count of pieces by one, or joins two points

already in the same piece, which closes a loop and reduces nothing. To get

from $n$ pieces to one piece requires exactly $n - 1$ of the first kind, and

any link of the second kind is paid for and connects nothing.

FIG 1Why the count is fixed before anything is chosen

: the number of points
: the number of links that each joined two separate pieces

A thousand buildings always need nine hundred and ninety nine cables, whatever the layout and whatever the costs. So the problem is never how many links to buy, only which ones, and a solution that contains a loop is strictly worse than the same solution with the dearest link of that loop removed.

The method

Sort all the links by cost. Go through them from cheapest to dearest, and take

each one if it joins two pieces that are not yet joined, and skip it if its

two ends are already in the same piece. Stop when $n - 1$ links have been

taken.

That is all of it. The only machinery needed is a way to ask whether two

points are already in the same piece, and a way to record that two pieces have

become one, which is a small structure that does both in almost constant time.

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