Graphs

Suppose that you have a directed graph G = (V,E) with an edge weight function w and a source vertex s V . The weights can be negative, but there are no negative weight cycles. Furthermore, assume that all edge weights are distinct (i.e. no two edges have the same weight). The single source shortest path problem is to find the shortest path distances from s to every vertex in V . (a) Suppose that you also guaranteed that for all v V , a shortest path from s to v has increasing edge weights. Give an algorithm to find the shortest path distances from s to every vertex in V . Analyze the running time of your algorithm and explain why it is correct. For full credit, your algorithm should run in time O(V + E logE). (b) A sequence is bitonic if it monotonically increases and then monotonically decreases, or if by a circular shift it monotonically increases and then monotonically decreases. For example the sequences (1,4,6,8,3,2), (9,2,4,10,5), and (1,2,3,4) are bitonic, but (1,3,12,4,2,10) is not bitonic. Now, suppose that the sequences of edge weights along the shortest paths are no longer guaranteed to be increasing, but instead are guaranteed to be bitonic. Give a single source shortest path algorithm, explain why it is correct, and analyze its running time. For full credit, your algorithm should run in time O(V + E logE).