Java Reference
In-Depth Information
ABCDE
Initial
0 1 1 1 1
Process A
0
10
3
20 1
Process C
0
5
3
20
18
Process B
0
5
3
10
18
Process D
0
5
3
10
18
Process E
0
5
3
10
18
Figure11.19
A listing for the progress of Dijkstra's algorithm operating on the
graph of Figure 11.16. The start vertex is A.
ity queue is more efficient when the graph is sparse because its cost is ((jVj +
jEj) logjEj). However, when the graph is dense, this cost can become as great as
(jVj
2
logjEj) = (jVj
2
logjVj).
Figure 11.19 illustrates Dijkstra's algorithm. The start vertex is A. All vertices
except A have an initial value of 1. After processing Vertex A, its neighbors have
their D estimates updated to be the direct distance from A. After processing C
(the closest vertex to A), Vertices B and E are updated to reflect the shortest path
through C. The remaining vertices are processed in order B, D, and E.
11.5
Minimum-Cost Spanning Trees
The minimum-cost spanning tree (MST) problem takes as input a connected,
undirected graph G, where each edge has a distance or weight measure attached.
The MST is the graph containing the vertices of G along with the subset of G's
edges that (1) has minimum total cost as measured by summing the values for all of
the edges in the subset, and (2) keeps the vertices connected. Applications where a
solution to this problem is useful include soldering the shortest set of wires needed
to connect a set of terminals on a circuit board, and connecting a set of cities by
telephone lines in such a way as to require the least amount of cable.
The MST contains no cycles. If a proposed MST did have a cycle, a cheaper
MST could be had by removing any one of the edges in the cycle. Thus, the MST
is a free tree with jVj 1 edges. The name “minimum-cost spanning tree” comes
from the fact that the required set of edges forms a tree, it spans the vertices (i.e.,
it connects them together), and it has minimum cost. Figure 11.20 shows the MST
for an example graph.
11.5.1 Prim's Algorithm
The first of our two algorithms for finding MSTs is commonly referred to as Prim's
algorithm. Prim's algorithm is very simple. Start with any Vertex N in the graph,
setting the MST to be N initially. Pick the least-cost edge connected to N. This
