2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

relax the edges once in increasing order and once in decreasing order.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .