For Exercises 21–24 use Kruskal’s algorithm to find the minimal spanning tree.
Section 7.3 Shortest Path and Minimal Spanning Tree
595
21. Graph for Exercises 1–4
22. Graph for Exercise 18
23. Graph for Exercise 19
24. Graph for Exercise 20
25. Give an example to show that adding the node closest to IN at each step, as is done in Prim’s minimal
spanning tree algorithm, will not guarantee a shortest path.
26. Let a be the arc of lowest weight in a weighted graph. Show that a must be an arc in any minimal spanning tree.
27. A city plans to lay out bike paths connecting various city parks. A map with the distances between the parks
is shown in the figure. (Some direct connections would have to cross major highways, so these distances
are not shown in the map.) Find which paths to pave so that all parks are connected but the cost is minimal.
3
7
2
5
2
4
6
5
4
4
3
2
28. Assume that arc weights represent distance. Then adding new nodes and arcs to a graph may result in a
spanning tree for the new graph that has less weight than a spanning tree for the original graph. (The new
spanning tree could represent a minimal-cost network for communications between a group of cities obtained by adding a switch in a location outside any of the cities.)
a. Find a spanning tree of minimum weight for the following labeled graph. What is its weight?
b. Put a node in the center of the square. Add new arcs from the center to the corners. Find a spanning tree
for the new graph, and compute its (approximate) weight.
29. At the beginning of this chapter, you received the following assignment:
You are the network administrator for a wide-area backbone network that serves your company’s many offices
across the country. Messages travel through the network by being routed from point to point until they reach
their destination. Each node in the network therefore acts as a switching station to forward messages to other
nodes according to a routing table maintained at each node. Some connections in the network carry heavy traffic, while others are less used. Traffic may vary with the time of day; in addition, new nodes occasionally come
on line and existing nodes may go off line. Therefore you must periodically provide each node with updated
information so that it can forward messages along the most efficient (that is, the least heavily traveled) route.
How can you compute the routing table for each node?
You realize that you can represent the network as a weighted graph, where the arcs are the connections
between nodes and the weights of the arcs represent traffic on the connections. The routing problem then becomes one of finding the shortest path in the graph from any node to any other node. Dijkstra’s algorithm can
be used to give the shortest path from any one node to all other nodes (see Exercise 9), so you could use the
algorithm repeatedly with different start nodes. Or you could use Floyd’s algorithm. Discuss the advantages
and disadvantages of each approach, including an analysis of the order of magnitude of each approach.
Section 7.3 Shortest Path and Minimal Spanning Tree
595
21. Graph for Exercises 1–4
22. Graph for Exercise 18
23. Graph for Exercise 19
24. Graph for Exercise 20
25. Give an example to show that adding the node closest to IN at each step, as is done in Prim’s minimal
spanning tree algorithm, will not guarantee a shortest path.
26. Let a be the arc of lowest weight in a weighted graph. Show that a must be an arc in any minimal spanning tree.
27. A city plans to lay out bike paths connecting various city parks. A map with the distances between the parks
is shown in the figure. (Some direct connections would have to cross major highways, so these distances
are not shown in the map.) Find which paths to pave so that all parks are connected but the cost is minimal.
3
7
2
5
2
4
6
5
4
4
3
2
28. Assume that arc weights represent distance. Then adding new nodes and arcs to a graph may result in a
spanning tree for the new graph that has less weight than a spanning tree for the original graph. (The new
spanning tree could represent a minimal-cost network for communications between a group of cities obtained by adding a switch in a location outside any of the cities.)
a. Find a spanning tree of minimum weight for the following labeled graph. What is its weight?
b. Put a node in the center of the square. Add new arcs from the center to the corners. Find a spanning tree
for the new graph, and compute its (approximate) weight.
29. At the beginning of this chapter, you received the following assignment:
You are the network administrator for a wide-area backbone network that serves your company’s many offices
across the country. Messages travel through the network by being routed from point to point until they reach
their destination. Each node in the network therefore acts as a switching station to forward messages to other
nodes according to a routing table maintained at each node. Some connections in the network carry heavy traffic, while others are less used. Traffic may vary with the time of day; in addition, new nodes occasionally come
on line and existing nodes may go off line. Therefore you must periodically provide each node with updated
information so that it can forward messages along the most efficient (that is, the least heavily traveled) route.
How can you compute the routing table for each node?
You realize that you can represent the network as a weighted graph, where the arcs are the connections
between nodes and the weights of the arcs represent traffic on the connections. The routing problem then becomes one of finding the shortest path in the graph from any node to any other node. Dijkstra’s algorithm can
be used to give the shortest path from any one node to all other nodes (see Exercise 9), so you could use the
algorithm repeatedly with different start nodes. Or you could use Floyd’s algorithm. Discuss the advantages
and disadvantages of each approach, including an analysis of the order of magnitude of each approach.