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.
Suppose that we are given a directed graph $G=(V, E)$ with weight function $w:E \to 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 \in V$, the weights of the edges along any shortest path from $s$ to $v$ form a bitonic sequence.
I need to find an algorithm to solve this problem, but can't think of anything more efficient than the brute force method. Does anyone have any suggestions?
Best Answer
relax the edges once in increasing order and once in decreasing order.