A cable company must use cables to connect 15 homes together so that every home is reachable by every other home. The company has estimated the costs of different cable routes (Figure 1-5 shows the numbers associated with each link). One engi- neer provides an algorithm, shown in Figure 1-5, that will find the cheapest set of routes to pick. Does the engineer's algorithm work for this case? Why or why not?
Engineer's Algorithm:
a. Pick one cable route with the lowest cost not already picked. Add this route to the set of cheapest routes.
b. Check if every house is connected to every other house through any series of cables. If it isn't, go back to step 1. If every house is connected, then the cheapest set of routes has been found.
