David, the chief executive officer of O’Reilly Auto Parts, is at his office in Springfield, Missouri, and wishes to visit his company’s distribution centers in the following locations: Bismarck, ND; Carson City, NV; Helena, MT; and Knoxville, TN. He wishes to visit each of these locations and return to his office in Springfield. The one-way flight prices are given in the table above and to the right.

a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of flights on the appropriate edges.

b) Use the nearest neighbor method to approximate the optimal route for David to travel to each city and return to Springfield. Give the cost of the route determined.

Transcribed Image Text:

Carson Bismarck City Helena Knoxville Springfield Bismarck $431 $483 $476 $378 Carson City $431 $144 $159 $505 Helena $483 $144 $542 $492 Knoxville $476 $159 $542 $459 Springfield $378 $505 $492 $459