Mr. Pleacher and his wife want to take a trip to visit his brother, his parents, and each of their children. Mr. Pleacher and his wife live in Stephens City, VA. (SC on the map below) Mr. Pleacher's brother lives in Leitchfield, KY. (L on the map) Mr. Pleacher's parents live in Owensboro, KY. (O on the map) Mr. Pleacher's daughter Elizabeth and her family live in Ponte Vedra Beach, FL. (PVB on the map) Mr. Pleacher's daughter Sarah and her family live in Fort Collins, CO. (FC on the map) Mr. Pleacher's son Michael and his wife live in Portland, ME. (P on the map) The distances between the cities are given below: Stephens City to Portland is 615 miles Stephens City to Ponte Vedra Beach is 758 miles Stephens City to Fort Collins 1,639 miles Stephens City to Leitchfield is 588 miles Stephens City to Owensboro 651 miles Owensboro to Ponte Vedra Beach is 744 miles Owensboro to Fort Collins is 1,111 miles Owensboro to Leitchfield is 65 miles Owensboro to Portland is 1,188 miles Ponte Vedra Beach to Portland is 1,280 miles Ponte Vedra Beach to Fort Collins is 1,824 miles Portland to Fort Collins is 2,070 miles Using the data above, help Mr. Pleacher and his wife plan a roundtrip to visit each relative without passing through any city more than once (except the return home to Stephens City). You may use only the routes indicated on the map -- there is only one road into Leitchfield and one road out (you must go through Stephens City or Owensboro to get there). Find the shortest path.

Solution to the Problem: The shortest paths are: SC - P - PVB - FC - O - L - SC and its reverse SC - L - O - FC - PVB - P - SC, which are both 5,483 miles. I used a tree diagram to examine all possible paths. Then I set up a table to find the shortest path(s). SC - P - FC - PVB - O - L - SC = 5,906 miles SC - P - PVB - FC - O - L - SC = 5,483 miles SC - L - O - PVB - P - FC - SC = 6,386 miles SC - L - O - PVB - FC - P - SC = 5,906 miles SC - L - O - P - PVB - FC - SC = 6,584 miles SC - L - O - P - FC - PVB - SC = 6,493 miles SC - L - O - FC - P - PVB - SC = 5,872 miles SC - L - O - FC - PVB - P - SC = 5,483 miles SC - PVB - P - FC - O - L - SC = 5,872 miles SC - PVB - FC - P - O - L - SC = 6,493 miles SC - FC - P - PVB - O - L - SC = 6,386 miles SC - FC - PVB - P - O - L - SC = 6,584 miles So, paths #2 and #8 above have the least mileage of 5,483 miles, a savings of 1,101 miles over routes #5 or 12.

Correctly solved by: