6.5 SHORTEST-PATH ALGORITHM 163
- Prove whether it is always, never, or sometimes true that the order in which
the nodes are added to the MST by the Dijkstra–Prim algorithm is the same
as the order in which they are encountered in a breadth-first traversal.
- Prove whether it is always, never, or sometimes true that the order in which
the nodes are added to the MST by the Dijkstra–Prim algorithm is the same
as the order in which they are encountered in a depth-first traversal.
6.5 Shortest-Path Algorithm
The shortest-path algorithm will find for two nodes the series of edges
between them that will result in the smallest total weight.
It might seem that we could use the minimum spanning tree algorithm to
prune out some of the edges and then just look for the path between the nodes
in the spanning tree. Unfortunately, that will not always produce the shortest
path. Remember that the minimum spanning tree algorithm is trying to find
an overall total that is smallest, so it is going to look for the smallest weights
possible. For example, think of a graph that is “circular” in shape. In other
words, the first node is connected to the second, which is connected to the
third, and so on until the last node, which is connected to the first. This graph
is just a ring where each node is just connected to the two nodes on either side
of it. For example, Fig. 6.7(a) shows just such a graph with six nodes. Notice
that weights on all of the edges are 1, except for the edge from node A to node
B, which has a weight of 2. The minimum spanning tree algorithm will pick all
of the edges with weight 1, and drop the one edge of weight 2. But that means
that the path between node A and node B in the minimum spanning tree (Fig.
6.7(b)) must go through all of the other nodes for a path length of 5. This is
A B
E D
F C
1
1
2
1
1
1
A B
E D
F C
1
1
1
1
1
■FIGURE 6.7A
A ring graph
■FIGURE 6.7B
Its minimum spanning tree
