Yilan lives in Boston, Massachusetts, and works for the e-commerce company Wayfair. Yilan wishes to visit company warehouses in the following locations: Madison, WI; Princeton, NJ; Salem, OR; and Walla Walla, WA. The one-way flight prices are given in the following table.

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 Yilan to travel to each city and return to Boston. Give the cost of the route determined.

Transcribed Image Text:

A Boston Boston Madison Princeton Salem Walla Walla Boston $131 $ 256 $298 $ 576 Madison $131 $ 154 $356 $ 970 Princeton $256 $154 $353 $1164 Salem $298 $356 $ 353 $ 179 Walla Walla $576 $970 $1164 $179