Question 6 - Traveling Salesman
Consider a traveling salesman who needs to visit 5 cities: A, B, C, D, and E. The distances (in kilometers) between the cities are as follows: A to B: 10 km A to C: 15 km A to D: 20 km A to E: 25 km B to C: 35 km B to D: 30 km B to E: 20 km C to D: 15 km C to E: 30 km D to E: 10 km What is the shortest possible route that the salesman can take, visiting each city exactly once and returning to the starting city? A) 70 km B) 85 km C) 90 km D) 100 km E) None of above