On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem, starting at A?
A) ABCDA
B) ABDCA
C) ACBDA
D) ABCD

Question

On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem, starting at A? 
A) ABCDA 
B) ABDCA 
C) ACBDA 
D) ABCD

Quizplus · Accepted Answer

The nearest-neighbor algorithm starts at A and chooses the closest unvisited city, which is B. Then it chooses the closest unvisited city from B, which is D. Then it chooses the closest unvisited city from D, which is C. Finally, it returns to A, since that is the only remaining unvisited city. Therefore, the routing produced by the nearest-neighbor algorithm starting at A is ABDCA.

On the Graph Below, Which Routing Is Produced by Using