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. For the bitonic euclidean traveling-salesman problem.

Suppose that we are given a directed graph G = (V, E) with weight function w : E → R, where all edge weights are unique, and we wish to find single-source shortest paths from a source vertex s. We are given one additional piece of information: for each vertex ν ∈ V, the weights of the edges along any shortest path from s to ν form a bitonic sequence.

Give the most efficient algorithm you can to solve this problem, and analyze its running time.