We define the bottleneck shortest path problem as follows. The length of a path is defined as the weight of heaviest edge on the path. The bottleneck shortest path between two vertices u and v is the length of the minimum length path (as defined above) between u and v. Suppose we are given an undirected, weighted graph G and a source s.

(a) If xand y are vertices on the bottleneck shortest path P from u to v, provide an example to show that the section of P between x and y does not have to be the bottleneck shortest path between x and y. However, if this is the case, show that we can replace this section by a bottleneck shortest path between x and y and the new path will still be a bottleneck shortest path between u and v.

(b) Using the observation from the previous part, show that there is a set of bottleneck shortest paths from s to every vertex that forms a tree.

(c) Describe an efficient algorithm to find this tree. (Hint: An algorithm we have seen in class will work.)

(d) Suppose we have found the bottleneck shortest paths from source s and we are given a new source vertex v. How fast can you now compute the bottleneck shortest path tree from v?

(e) Now suppose G is a directed graph and we are again given a source vertex s. Describe an efficient algorithm to find the bottleneck shortest paths from s to all vertices.