Our college curling team doesn’t have a lot of money, but would like to set up a season of away
games. The coach has found that he can arrange games with the Columbus, Dallas, Houston,
Kansas City and Louisville teams, and wants to arrange a season at the lowest possible cost. The
team travels by bus, so lowest mileage should result in lowest cost.
The distances between the cities are given below.
Home Columbus Dallas Houston Kansas City Louisville
Home * 533 795 789 798 382
Columbus 533 * 1028 1137 656 209
Dallas 795 1028 * 243 289 819
Houston 789 1137 243 * 710 928
Kansas City 798 656 289 710 * 520
Louisville 382 209 819 928 520 *
1. Draw a weighted graph that corresponds to this situation.
2. Devise a way using the cheapest link algorithm that the team can visit all five cities and
return home. Give the weight of the circuit.
3. Using the Repetitive Nearest Neighbor algorithm, find another relatively efficient
Hamilton circuit for the curling team, starting and ending at home. Give the weight of
the circuit.