24-6 Bitonic shortest paths

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 $\langle 1, 4, 6, 8, 3, -2 \rangle$, $\langle 9, 2, -4, -10, -5 \rangle$, and $\langle 1, 2, 3, 4 \rangle$ are bitonic, but $\langle 1, 3, 12, 4, 2, 10 \rangle$ is not bitonic. (See Problem 15-3 for the bitonic euclidean traveling-salesman problem.)

Suppose that we are given a directed graph $G = (V, E)$ with weight function $w: E \to \mathbb 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.

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

We'll use the Bellman-Ford algorithm, but with a careful choice of the order in which we relax the edges in order to perform a smaller number of $\text{RELAX}$ operations. In any bitonic path there can be at most two distinct increasing sequences of edge weights, and similarly at most two distinct decreasing sequences of edge weights. Thus, by the path-relaxation property, if we relax the edges in order of increasing weight then decreasing weight twice (for a total of four times relaxing every edge) the we are guaranteed that $v.d$ will equal $\delta(s, v)$ for all $v \in V$ . Sorting the edges takes $O(E\lg E)$. We relax every edge $4$ times, taking $O(E)$. Thus the total runtime is $O(E\lg E) + O(E) = O(E\lg E)$, which is asymptotically faster than the usual $O(VE)$ runtime of Bellman-Ford.