EXAMPLE 6 Applying the Sorted-Edges Algorithm Revisited

Although the edges selected by applying the sorted-edges method to the example in Figure 2.3 are connected to each other at every stage, this does not always happen. For example, if we apply the sorted-edges algorithm to the graph in Figure 2.10a, we build up the tour first with edge ED (400) and then edge BC (500), which do not touch. The edges that are then selected are AD,AB, and EC, giving the circuit EDABCE, which is the same as the nearest-neighbor circuit starting at vertex A. Note we must sort numbers in order to find 5 edges.