Jennifer is the sales manager for AT&T for the state of Missouri. There are major sales offices in Columbia, Kansas City, St. Joseph, St. Louis, and Springfield. The distances in miles between these cities are given in the following table.

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

(b) Use the nearest neighbor method to approximate the optimal route for Jennifer to begin in St. Joseph, visit each city once, and return to St. Joseph.

(c) Suppose that Jennifer starts in Springfield. Use the nearest neighbor method to approximate the optimal route for Jennifer to visit each city once and return to Springfield.

Transcribed Image Text:

Kansas St. St. Columbia City Joseph Louis Springfield Columbia 130 177 127 168 Kansas City 130 54 256 192 St. Joseph St. Louis 177 54 304 224 127 256 304 210 Springfield 168 192 224 210