Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 177

Fig. 8-35

ThusACDBAwith weight 20 is the Hamiltonian circuit of minimum weight.
We solved the “traveling-salesman problem” for the weighted complete graph in Fig. 8-35(a)by list-
ing and finding the weights of its three possible Hamiltonian circuits. However, for a graph with many ver-
tices, this may be impractical or even impossible. For example, a complete graph with 15 vertices has over
40 million Hamiltonian circuits. Accordingly, for circuits with many vertices, a strategy of some kind is needed
to solve or give an approximate solution to the traveling-salesman problem. We discuss one of the simplest
algorithms here.

Nearest-Neighbor Algorithm

The nearest-neighbor algorithm, starting at a given vertex, chooses the edge with the least weight to the
next possible vertex, that is, to the “closest” vertex. This strategy is continued at each successive vertex until a
Hamiltonian circuit is completed.

EXAMPLE 8.6 LetGbe the weighted graph given by the table in Fig. 8-35(b). That is,Ghas the vertices
P,Q,...,T, and the distance fromPtoQis 18, fromPtoRis 22, and so on until the distance fromTtoSis

13. We apply the nearest-neighbor algorithm toGstarting at: (a)P, (b)Q.

(a) Starting atP, the first row of the table shows us that the closest vertex toPisSwith distance 15. The fourth

row shows that the closest vertex toSisQwith distance 12. The closest vertex toQisRwith distance 11.

FromR, there is no choice but to go toT with distance 10. Finally, fromT, there is no choice but to go

back toPwith distance 20. Accordingly, the nearest-neighbor algorithm beginning atPyields the following

weighted Hamiltonian circuit:

|PSQRTP|= 15 + 12 + 11 + 10 + 20 = 68

(b) Starting atQ, the closest vertex isRwith distance 11; fromRthe closest is T with distance 10; and fromT

the closest isSwith distance 13. FromSwemustgo toPwith distance 15; and finally fromPwe must go

back toQwith distance 18.Accordingly, the nearest-neighbor algorithm beginning atQyields the following

weighted Hamiltonian circuit:

|QRTSPQ|= 11 + 10 + 13 + 15 + 18 = 67

The idea behind the nearest-neighbor algorithm is to minimize the total weight by minimizing the weight
at each step. Although this may seem reasonable, Example 8.6 shows that we may not get a Hamiltonian cir-
cuit of minimum weight; that is, it cannot be both 68 and 67. Only by checking allH=(n− 1 )!/ 2 = 12
Hamiltonian circuits ofGwill we really know the one with minimum weight. In fact, the nearest-neighbor
algorithm beginning atAin Fig. 8-35(a)yields the circuitACBDAwhich has the maximum weight. However, the
nearest-neighbor algorithm usually gives a Hamiltonian circuit which is relatively close to the one with minimum
weight.