Answers · Making it fast enough

Why is it safe to keep taking the cheapest link that doesn't create a loop?

In shortBecause the cheapest link joining two separate pieces is the cheapest way across a split, and swapping it into any rival solution cannot raise the total cost.

It is safe because the cheapest link joining two separate pieces is the cheapest way across a split, and swapping it into any rival solution cannot raise the total cost. The method never has to undo a choice: every link it takes is one that some cheapest overall set of links could have taken, and the reason is an exchange rather than luck.

The count comes first

Before any cost matters, the number of links is settled. Start with n separate pieces. A link that joins two pieces reduces the number of pieces by one; a link whose ends are already in one piece closes a loop and reduces nothing, because those points were connected by another route already. To reach one piece from n needs n - 1 reducing links. So a joining with a loop is never a candidate for cheapest: remove any link from that loop and everything is still joined, at lower or equal cost. The only question is which n - 1 links to buy.

n - k \text{ pieces after } k \text{ reducing links, so } k = n - 1 \text{ to reach one piece.}

The exchange

A cut is a division of the points into two groups, any two groups. Let e be the cheapest link with one end in each group. The claim is that some cheapest joining contains e. Take a cheapest joining T that does not contain e and add e to it. Since T already joined everything, adding e creates exactly one loop. That loop leaves the first group along e and must return to it, so it contains another link f crossing the same division. Remove f. The result still joins every point, because the only connection broken was on a loop. Its cost is the old cost plus the cost of e minus the cost of f, and e is no dearer than f by choice, so the cost did not rise.

C(T') = C(T) + c(e) - c(f) \le C(T), \qquad c(e) \le c(f).

At the moment the method takes a link, let A be one of the two pieces it is joining. If a cheaper crossing from A to outside had been available then, its ends were in different pieces then, so the method would already have taken it. Therefore the chosen link is the cheapest crossing between A and everything else, and the exchange applies to that division. The argument is local but not optimistic: it proves that this particular choice cannot be regretted, not that taking the cheapest option is generally wise.

FIG 1Choosing links cheapest first

step	cost	link	ends already joined	decision	pieces remaining	what happened
1	1	a to c	no	take it	4	cheapest link overall
2	2	b to d	no	take it	3	joins two new pieces
3	3	c to d	no	take it	2	merges the two pieces into one
4	4	a to b	yes, through c and d	skip it	2	would close the loop a-c-d-b-a
5	5	d to e	no	take it	1	finishes the joining
6	6	a to e	yes	skip it	1, finished	four links taken, as required

6 steps

Five points need four links. The taken costs are 1, 2, 3 and 5, so the total is 11; the links costing 4 and 6 are skipped because their ends are already joined.

Where the instinct fails

The natural guess is that taking the cheapest available link is safe because cheap choices are bound to add up. They are not. Suppose a traveller wants the cheapest route from S to T. The road S to A costs 1 and A to T costs 100, so that route costs 101. The road S to B costs 2 and B to T costs 2, so that route costs 4. Taking the cheapest first road chooses S to A and commits to 101, while the better route starts with the dearer first road. A joining problem has no such commitment because a link that closes a loop is simply refused, and a link that joins two pieces can be exchanged into an optimum. The difference is the exchange, not the cheapness.

The guarantee needs undirected links, known costs, and the aim of joining everything once. If a loop is required, as in a tour, the cheapest non-looping link can force a later expensive link; if links have capacities, or the task is to make one named pair close rather than to join all points, the exchange has no loop to remove. Ties do not matter: if two crossings cost the same, either can be exchanged for the other, and the total is unchanged. Negative costs also do not break the exchange, because it only compares two crossing links, though they make the fixed count of n - 1 links more important than ever.

Worth keeping

Every joining of n points uses exactly n - 1 links, so any loop is paid for and connects nothing.
A cheapest link across a division of the points belongs to some cheapest overall joining, because adding it and removing a dearer crossing leaves everything joined at no greater cost.
Choosing the cheapest first road can still produce a route far more expensive than the best one; the exchange property is what makes the joining problem different.

Where this goes next

This question is one step of Graphs and Finding a Path, a course that works through its subject from the beginning. The page that teaches this part of it is Connecting Everything Cheaply, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course