Several oil companies are jointly planning to build an oil pipeline to connect several southwestern and midwestern cities. The miles between cities are shown in the following table:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1. Albuquerque |
|
400 |
|
520 |
|
|
|
750 |
|
|
| 2. Denver |
400 |
|
450 |
490 |
|
|
|
|
|
|
| 3. Omaha |
|
450 |
|
580 |
210 |
120 |
|
|
|
|
| 4. Oklahoma City |
520 |
490 |
580 |
|
310 |
|
|
240 |
|
|
| 5. Kansas City |
|
|
210 |
310 |
|
175 |
260 |
340 |
|
|
| 6. Des Moines |
|
|
120 |
|
175 |
|
250 |
|
250 |
|
| 7. St. Louis |
|
|
|
|
260 |
250 |
|
270 |
235 |
320 |
| 8. Little Rock |
750 |
|
|
240 |
340 |
|
270 |
|
|
340 |
| 9. Indianapolis |
|
|
|
|
|
250 |
235 |
|
|
260 |
| 10. Nashville |
|
|
|
|
|
|
320 |
340 |
260 |
Determine a pipeline system that will connect all 10 cities using the minimum number of miles of pipe, and indicate how many miles of pipe will be used.