Chapter 13.3, Problem 32E

Cranberry Plants Altay lives in Boston, Massachusetts, and works for Ocean Spray Cranberries, Inc. Altay wishes to visit cranberry farms in the following locations: Madison, Wisconsin: Princeton, New Jersey, Salem, Oregon; and Walla Walla, Washington. The one-way flight prices are given in the following table.

	Boston	Boston	Princeton	Princeton	Walla Walla
Boston	*	$131	$256	$298	$576
Boston	$131	*	$154	$356	$970
Princeton	$256	$154	*	$353	$1164
Princeton	$298	$356	$353	*	$179
Walla Walla	$576	$970	$1164	$179	*

1. a. Represent this traveling salesman problem with a complete, weighted graph showing the prices of flights on the appropriate edges.
2. b. Use the nearest neighbor method to approximate the optimal route for Jim to travel to each city and return to Springfield Give the cost of the route determined.
3. c. Randomly select another route for Jim to travel from Springfield to each of the other cities and return to Springfield and then compute the cost of this route Compare this cost with the cost determined in part (b).