EXAMPLE 4 Applying the Nearest-Neighbor Algorithm Revisited
Figure 2.10 again illustrates the ease of applying the nearest-neighbor algorithm, this time to a weighted complete graph with five vertices. Starting at vertex A, we get the tour ADECBA (cost 2800) (Figure 2.10a). Note that the nearest-neighbor algorithm starting at vertex B yields the tour BCADEB (cost 3050) (Figure 2.10b).
49
Figure 2.10: Figure 2.10 (a) A weighted complete graph with five vertices that illustrates the use of the nearest-neighbor algorithm (starting at A). (b) TSP tour generated by the nearest-neighbor algorithm (starting at B).