This is problem 24-6 from the text hook. A sequence is bitonic if it monotonical

Question

This is problem 24-6 from the text hook. A sequence is bitonic if it monotonically increases and then monotonically decreases, or if after 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 rightarrow 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 V, the weights of the edges along any shortest path from s to v from a bitonic sequence. Give the most efficient algorithm you can to solve this problem, and analyze its running time.

Explanation / Answer

for each vertex v V, the weights of the edges alongany shortest path from s to v are increasing. Then we could call INITIALIZESINGLE-SOURCE and then just relax all edges one time, going in increasing orderof weight. Then the edges along every shortest path would be relaxed in order oftheir appearance on the path.

We perform four passes, relaxing each edge once in each pass. The 1st and third passes relax edges in increasing order of weight, and the second and fourth passes in decreasing order. Again, by the path-relaxation property and the uniqueness of edge weights, we have computed correct shortest paths.

The total time is O(V + E lg V), as follows.

The time to sort |E| edges by weight is O(E lg E) = O(E lg V) (since |E| = O(V2)).

INITIALIZE-SINGLE-SOURCE takes O(V ) time.

Each of the four passes takes O(E) time.

Thus, the total time isO(E lg V + V + E) = O(V + E lg V).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.