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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用