# Chapter 8

## Contents

# Weighted Graph Algorithms

### Simulating Graph Algorithms

- 8.1. For the graphs in Problem 7-1:
- (a) Draw the spanning forest after every iteration of the main loop in Kruskal’s algorithm.
- (b) Draw the spanning forest after every iteration of the main loop in Prim’s algorithm.
- (c) Find the shortest-path spanning tree rooted in .
- (d) Compute the maximum flow from to .

### Minimum Spanning Tree

- 8.2. Is the path between two vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

- 8.3. Assume that all edges in the graph have distinct edge weights (i.e., no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

- 8.4. Can Prim’s and Kruskal’s algorithms yield different minimum spanning trees? Explain why or why not.

- 8.5. Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Explain why or why not.

- 8.6. (a) Assume that all edges in the graph have distinct edge weights (i.e., no pair of edges have the same weight). Is the
*minimum spanning tree*of this graph unique? Give a proof or a counterexample. - (b) Again, assume that all edges in the graph have distinct edge weights (i.e. no pair of edges have the same weight). Is the
*shortest-path spanning tree*of this graph unique? Give a proof or a counterexample.

- 8.7. Suppose we are given the minimum spanning tree of a given graph (with vertices and edges) and a new edge of weight that we will add to . Give an efficient algorithm to find the minimum spanning tree of the graph . Your algorithm should run in time to receive full credit.

- 8.8. (a) Let be a minimum spanning tree of a weighted graph . Construct a new graph by adding a weight of to every edge of . Do the edges of form a minimum spanning tree of ? Prove the statement or give a counterexample.
- (b) Let describe a shortest path between vertices and of a weighted graph . Construct a new graph by adding a weight of to every edge of . Does describe a shortest path from to in ? Prove the statement or give a counterexample.

- 8.9. Devise and analyze an algorithm that takes a weighted graph and finds the smallest change in the cost to a non-minimum spanning tree edge that would cause a change in the minimum spanning tree of . Your algorithm must be correct and run in polynomial time.

- 8.10. Consider the problem of finding a minimum-weight connected subset of edges from a weighted connected graph . The weight of is the sum of all the edge weights in .
- (a) Why is this problem not just the minimum spanning tree problem? (Hint: think negative weight edges.)
- (b) Give an efficient algorithm to compute the minimum-weight connected subset .

- 8.11. Let be a minimum spanning tree of a given graph with positive edge weights. Now suppose the weight of a particular edge is modified from to a new value . We seek to update the minimum spanning tree to reflect this change without recomputing the entire tree from scratch. For each of the following four cases, give a linear-time algorithm to update the tree:
- (a) and
- (b) and
- (c) and
- (d) and

- 8.12. Let be an undirected graph. A set of edges is called a
*feedback-edge set*if every cycle of has at least one edge in . - (a)Suppose that is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
- (b)Suppose that is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.

### Union Find

- 8.13. Devise an efficient data structure to handle the following operations on a weighted directed graph:
- (a)Merge two given components.
- (b)Locate which component contains a given vertex .
- (c)Retrieve a minimum edge from a given component.

- 8.14. Design a data structure that can perform a sequence of,
*union*and*find*operations on a universal set of elements, consisting of a sequence of all*unions*followed by a sequence of all*finds*, in time .

### Shortest Paths

- 8:15. The
*single-destination shortest path*problem for a directed graph seeks the shortest path*from*every vertex to a specified vertex . Give an efficient algorithm to solve the single-destination shortest paths problem.

- 8.16. Let be an undirected weighted graph, and let be the shortest-path spanning tree rooted at a vertex . Suppose now that all the edge weights in are increased by a constant number . Is still the shortest-path spanning tree from ?

- 8.17. (a)Give an example of a weighted connected graph and a vertex , such that the minimum spanning tree of is the same as the shortest-path spanning tree rooted at .
- (b)Give an example of a weighted connected directed graph and a vertex , such that the minimum-cost spanning tree of is very different from the shortest-path spanning tree rooted at .
- (c)Can the two trees be completely disjointed?

- 8.18. Either prove the following or give a counterexample:
- (a)Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
- (b)Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

- 8.19. Give an efficient algorithm to find the shortest path from to in an undirected weighted graph with positive edge weights, subject to the constraint that this path must pass through a particular vertex .

- 8.20. In certain graph problems, vertices have can have weights instead of or in addition to the weights of edges. Let be the cost of vertex , and the cost of the edge . This problem is concerned with finding the cheapest path between vertices and in a graph . The cost of a path is the sum of the costs of the edges and vertices encountered on the path.
- (a)Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of ). Assume that for all vertices (i.e., all vertices have the same cost). Give an
*efficient*algorithm to find the cheapest path from to and its time complexity. - (b)Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an
*efficient*algorithm to find the cheapest path from to and its time complexity. - (c)Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an
*efficient*algorithm to find the cheapest path from to and its time complexity.

- 8.21. Give an algorithm that takes an -vertex directed graph with positive edge lengths, and returns the length of the shortest cycle in the graph. This length is in the case of an acyclic graph.

- 8.22. A highway network is represented by a weighted graph , with edges corresponding to roads and vertices corresponding to road intersections. Each road is labeled with the maximum possible height of vehicles that can pass through the road. Give an efficient algorithm to compute the maximum possible height of vehicles that can successfully travel from to . What is the runtime of your algorithm?

- 8.23. You are given a directed graph with possibly negative weighted edges, in which the shortest path between any two vertices is guaranteed to have at most edges. Give an algorithm that finds the shortest path between two vertices and in time.

- 8.24. Can we solve the single-source
*longest*-path problem by changing*minimum*to*maximum*in Dijkstra’s algorithm? If so, then prove your algorithm correct. If not, then provide a counterexample.

- 8.25. Let be a weighted acyclic directed graph with possibly negative edge weights. Design a linear-time algorithm to solve the single-source shortest-path problem from a given source .

- 8.26. Let be a directed weighted graph such that all the weights are positive. Let and be two vertices in and be an integer. Design an algorithm to find the shortest path from to that contains exactly edges. Note that the path need not be simple.

- 8.27.
*Arbitrage*is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with U.S. dollars---a profit of 5%. Suppose that there are currencies and an table of exchange rates, such that one unit of currency buys units of currency . Devise and analyze an algorithm to determine the maximum value of Hint: think all-pairs shortest path.

### Network Flow and Matching

- 8.28. A matching in a graph is a set of disjoint edges—that is, edges that do not have common vertices. Give a linear-time algorithm to find a maximum matching in a tree.

- 8.29. An edge cover of an undirected graph is a set of edges such that each vertex in the graph is incident to at least one edge from the set. Give an efficient algorithm, based on matching, to find the minimum-size edge cover for .

Back to Chapter List