1. Run Dijkstra's algorithm on the following directed graph, starting at vertex 1. After each iteration of the outer loop, show the contents of the queue Q (the vertices in the queue and their keys). What are the final distances (in the distance[] array)?
(For example, suppose the vertices represent cities, the edges represent roads, and the weight WT(u,v) of an edge (u,v) is the clearance of the lowest bridge on the road from u to v. Then max_bottleneck(s,v) is the height of the largest truck that can get from s to v.)
2A: For each vertex v in the graph for problem 1, what is max_bottleneck(s,v)?
2B: Describe a linear-time algorithm for maximum bottleneck paths that works for acyclic digraphs. Give a high-level description and pseudo-code.
If G has edge weights, the weight of a tree T is the sum of the weights of the edges in the tree T.
The minimum spanning tree problem is to find a spanning tree T (of a graph G with edge weights) of minimum possible weight.
3A: What is the weight of the minimum-weight spanning tree in the graph above? What are the edges of the tree?
3B: Claim: in any graph G with edge weights, there is only one spanning tree of minimum total weight. (That is, if T and T' are two different spanning trees, then only one of them can be a minimum spanning tree.)
Prove or disprove this claim.
3C: Claim: in any graph G, the highest-weight edge cannot be in any minimum spanning tree of G.
Prove or disprove this claim.
Describe how you would design an algorithm to do this.
Modify this algorithm to instead compute single-source maximum bottleneck paths (defined in problem 2, above.) Describe the high-level idea of your modification, and give pseudo-code too.