In this section we define the minimum-cost spanning tree problem and a related path-finding problem. We give a recurrence for solving the path-finding problem via dynamic programming. We then prove that the solution to the path-finding problem contains the solution to the minimum-cost spanning tree problem.

Given an *n*-node connected undirected graph ,
where *V* is the set , and where each edge
in *E* has cost , the minimum-cost spanning tree
problem is to find a subgraph that connects the vertices in *V* such
that the sum of the costs of the edges in the subgraph is minimum. We
assume that the edge costs are unique. (If not, lexicographical
information can be added to make them unique.) For convenience, we
also assume that if is not in *E* then it has cost .

The path-finding problem is to compute the cost for each of the shortest (lowest-cost) path from *i* to *j* that
passes through vertices only in the set , where
*the cost of a path is defined to be the highest cost of any edge
on the path*. For any *i* and *j*, the shortest path from *i* to *j*
with no intermediate vertex higher than *k* either passes through *k*
or does not. In the first case, the cost of the shortest path from
*i* to *j* is either the cost of the shortest path from *i* to *k* or
the cost of the shortest path from *k* to *j*, whichever is higher.
In the second case, we have . Thus,
can be computed by the recurrence

The following theorem shows that the unique minimum-cost spanning tree can be recovered from the costs of the shortest paths.

*Proof:*
The proof has two parts. We first show that if is a tree
edge then . We then show that if then the edge is in the tree. First, assume that
is a tree edge, but that .
Consider the cut of the graph that crosses, but no other
tree edge crosses. Since , there must be
some path from *i* to *j* whose highest-cost edge has cost . Hence, every edge on this path has cost less than
. This path must cross the cut at least once. Replacing
the edge by any edge on the path that crosses the cut
reduces the cost of the tree, a contradiction. Conversely, assume
that , but that is not a tree edge.
Adding the edge to the tree forms a cycle whose highest-cost
edge costs more than than . Replacing this edge by
yields a tree with smaller cost, a contradiction. width 4pt height 8pt depth 1.5pt

Sun Jul 21 23:35:52 EDT 1996