perform on the order of n − 1 operations on the first pass, then n − 2, then n − 3,
and so on. But, as proof by induction will show,
(n − 1) + (n − 2) + c + 1 = (n − 1)n∙2 = Θ(n
2
)
Thus the worst-case situation still requires Θ(n
2
) operations.
Minimal spanning tree Problem
A problem encountered in designing networks is how to connect all the nodes efficiently, where nodes can be computers, telephones, warehouses, pumping stations,
and so on. A minimal spanning tree may provide an economical solution, one that
requires the least cable, pipeline, or whatever the connecting medium is. For reliability, however, the minimal spanning tree usually would be supplemented with
additional arcs so that if one connection were broken for some reason, an alternative route could be found.
Definition sPANNiNG tRee
A spanning tree for a connected graph is a nonrooted tree whose set of nodes
coincides with the set of nodes for the graph and whose arcs are (some of) the
arcs of the graph.
A spanning tree thus connects all the nodes of a graph with no excess arcs (no
cycles). There are algorithms for constructing a minimal spanning tree, a spanning tree with minimal weight, for a given simple, weighted, connected graph.
One of these algorithms, called Prim’s algorithm, proceeds very much like Dijkstra’s algorithm. There is a set IN, which initially contains one arbitrary node. For
every node z not in IN, we keep track of the shortest distance d 3z 4 between z and
any node in IN. We successively add nodes to IN, where the next node added is one
that is not in IN and whose distance d 3z 4 is minimal. The arc having this minimal
distance is then made part of the spanning tree. Because there may be ties between
minimal distances, the minimal spanning tree of a graph may not be unique. The
algorithm terminates when all nodes of the graph are in IN.
The key difference in the implementation of the two algorithms comes in the
computations of new distances for the nodes not yet in IN. In Dijkstra’s algorithm,
if p is the node that has just been added to IN, distances for non-IN nodes are
recalculated by
d 3z 4 = min(d 3z 4, d 3 p 4 + a3 p, z 4)
that is, by comparing the current distance of z from x with the distance of p from
x plus the distance of z from p. In Prim’s algorithm, if p is the node that has just
been added to IN, distances for non-IN nodes are recalculated by
d 3z 4 = min(d 3z 4, a3 p, z 4)
that is, by comparing the current distance of z from IN with the distance of z from p.
We won’t write out the algorithm (which, like Dijkstra’s algorithm, requires
Θ(n
2
) operations in the worst case and is a greedy algorithm); we will simply
illustrate it with an example.
Section 7.3 Shortest Path and Minimal Spanning Tree
587
and so on. But, as proof by induction will show,
(n − 1) + (n − 2) + c + 1 = (n − 1)n∙2 = Θ(n
2
)
Thus the worst-case situation still requires Θ(n
2
) operations.
Minimal spanning tree Problem
A problem encountered in designing networks is how to connect all the nodes efficiently, where nodes can be computers, telephones, warehouses, pumping stations,
and so on. A minimal spanning tree may provide an economical solution, one that
requires the least cable, pipeline, or whatever the connecting medium is. For reliability, however, the minimal spanning tree usually would be supplemented with
additional arcs so that if one connection were broken for some reason, an alternative route could be found.
Definition sPANNiNG tRee
A spanning tree for a connected graph is a nonrooted tree whose set of nodes
coincides with the set of nodes for the graph and whose arcs are (some of) the
arcs of the graph.
A spanning tree thus connects all the nodes of a graph with no excess arcs (no
cycles). There are algorithms for constructing a minimal spanning tree, a spanning tree with minimal weight, for a given simple, weighted, connected graph.
One of these algorithms, called Prim’s algorithm, proceeds very much like Dijkstra’s algorithm. There is a set IN, which initially contains one arbitrary node. For
every node z not in IN, we keep track of the shortest distance d 3z 4 between z and
any node in IN. We successively add nodes to IN, where the next node added is one
that is not in IN and whose distance d 3z 4 is minimal. The arc having this minimal
distance is then made part of the spanning tree. Because there may be ties between
minimal distances, the minimal spanning tree of a graph may not be unique. The
algorithm terminates when all nodes of the graph are in IN.
The key difference in the implementation of the two algorithms comes in the
computations of new distances for the nodes not yet in IN. In Dijkstra’s algorithm,
if p is the node that has just been added to IN, distances for non-IN nodes are
recalculated by
d 3z 4 = min(d 3z 4, d 3 p 4 + a3 p, z 4)
that is, by comparing the current distance of z from x with the distance of p from
x plus the distance of z from p. In Prim’s algorithm, if p is the node that has just
been added to IN, distances for non-IN nodes are recalculated by
d 3z 4 = min(d 3z 4, a3 p, z 4)
that is, by comparing the current distance of z from IN with the distance of z from p.
We won’t write out the algorithm (which, like Dijkstra’s algorithm, requires
Θ(n
2
) operations in the worst case and is a greedy algorithm); we will simply
illustrate it with an example.
Section 7.3 Shortest Path and Minimal Spanning Tree
587