The Minimal Spanning Tree Problem

In the shortest route problem presented in the previous section, the objective was to determine the shortest routes between the origin and the destination nodes in the network. In our example, we determined the best route from Los Angeles to each of the six destination cities. The minimal spanning tree problem is similar to the shortest route problem, except that the objective is to connect all the nodes in the network so that the total branch lengths are minimized. The resulting network spans $($connects$)$ all the points in the network at a minimum total distance $($or length$).$

To demonstrate the minimal spanning tree problem, we will consider the following example. The Metro Cable Television Company is to install a television cable system in a community con$-$ sisting of seven suburbs. Each of the suburbs must be connected to the main cable system. The cable television company wants to lay out the main cable network in a way that will minimize the total length of cable that must be installed. The possible paths available to the cable television company $($by consent of the town council$)$ and the feet of cable $($in thousands of feet$)$ required for each path are shown in Figure $7\mathrm{.}11.$