A spanning tree is defined as a tree that “spans” or connects together all nodes in a graph. Alternatively (and equivalently), a spanning tree is a connected acyclic graph. A spanning tree for a...

A spanning tree is defined as a tree that “spans” or connects together all nodes in a graph. Alternatively (and equivalently), a spanning tree is a connected acyclic graph. A spanning tree for a network with N nodes will have N 1 links and no cycles. A minimum spanning tree is a spanning tree having minimum total arc length. A number of very efficient algorithms exist for finding minimum spanning trees given a set of arc lengths for links in a network. The minimum spanning tree is useful in a number of contexts including network planning in developing countries and as an input to other algorithms including heuristics for the traveling salesman problem.

Consider the network shown in Figure 2.53. The minimum spanning tree is shown by the bold links. Note that the total length of the links in the minimum spanning tree is 29 units. Find the six shortest path trees (one rooted at each node).

What if anything is the relationship between the minimum spanning tree and the shortest path trees on a network?