If for a complete graph (or one with very few edges missing), our data is an n × n distance table (as in Prob. 13), show that the present algorithm [which is O(n²)] cannot easily be replaced by an algorithm of order less than O(n²).

Data from Prob. 13

Find a shortest spanning tree in the complete graph of all possible 15 connections between the six cities given (distances by airplane, in miles, rounded). Can you think of a practical application of the result?

Transcribed Image Text:

Denver Los Angeles Dallas New York Washington, DC 900 1800 1300 850 650 1200 1500 2350 200 Chicago 800 700 1350 Dallas 650 1650 2500 Denver Los Angeles New York