Laying Roads

---

A number of cities and the distances between them are given to you. You need to lay roads of minimum length connecting all the cities. There is no need to connect every city to the other directly. For example, consider the cities and their distances (in Km) given in the Table below.

	A	B	C	D	E	F	G
A	0
B	17	0
C	38	92	0
D	84	85	5	0
E	66	87	15	80	0
F	74	67	68	58	90	0
G	64	46	22	25	11	40	0

---

How do we get the answer?

This is one of the nice problems in Computer Science because the solution is very simple: just be greedy!!

What do we mean by that? Well, just pick the cities that are nearest to one another and lay roads connecting them. If you look at the Distances Table, the nearest cities are C and D which are only 5 Km apart. Therefore, lay a road between them.

Which are the next two nearest cities? They are E and G which are 11 Km from each other. So, lay another road there. Arguing similarly, we lay roads of lengths 15 Km (connecting C and E) and 17 Km (A and B).

Are we done yet? No, because we have not yet connected all the cities. Let us pick the next nearest: they are C and G with 22 Km between them. Should we lay this road? No, because C and G are already connected by going through E. Remember that we are very greedy!

What next? The next pair to consider are D and G (25 Km), but they too are already connected through C and E. But, when we go to the next pair A and C (38 Km), we are OK. A and C are not yet connected. So, we lay that road.

After that, we see that F and G are 40 Km apart and they are not connected yet. Lay that road and now examine the situation. All the cities are connected and therefore we can stop. The problem is solved!

The correct roads, with a total distance of 126 Km, are marked in red colour.

---

How do we know that we are correct?

Correctness here means that there should be no other set of roads which result in a shorter total distance (i.e., less than 126 Km). It is easy enough to show that no such set of roads exists.

How many roads are there in our solution? 6. How many cities? 7. Can you convince yourselves that we need N-1 roads to connect N cities? That is, if there are 4 cities, we need three roads; if there are 10, we need 9; and, if there are 100 cities, we need 99.

So, we need 6 roads for our solution. Let us replace one of them with any other road. Let us say, that we replace the road between F and G with one between B and F. But, that road is 67 Km long which is more than the one in our solution. As we picked cities starting from the nearest in order, we cannot pick any other distance from the remaining ones.

What about the ones that we looked at but did not pick? Say the one between C and G which was 22 Km long. Let us say, we picked it. Then, to connect the 7 cities, we need to pick 7 roads because the new one did not connect any new cities: C and G were already connected. If we say, we will replace one of the roads with the one between C and G so that we connect two new cities, then the roads we need to replace are the ones between C and E or E and G. But, they are shorter than 22 Km!

Therefore, there is no way to improve the solution. The greedy approach is the best!

---

Can a greedy approach always be used?

Unfortunately, no! Greedy does not always work. In fact, greed pays only for a few problems. But, when greedy works, it is wonderful: very simple and also quite fast.

Can we look at a problem and say that we can use a greedy approach? The answer is a bit involved and requires a fair amount of mathematical knowledge. But, we can give a rule of thumb that works most of the time.

First, does the problem ask for something extreme? Such as best, worst, tallest, longest, shortest, farthest, etc. Second, Look at all the possible solutions: if they all have a constant or fixed size, then greedy has a very high chance of working. In the problem given, note that all the solutions require 6 roads (in general, N-1 roads between N cities), therefore, the solution has a fixed size. And, not surpisingly, greedy worked.