AzulR's blog

By AzulR, history, 10 months ago, In English,

Can someone help me solve this problem? (_Introduction to Algorithms, Second Edition_: problem 24-6)

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 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→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 form a bitonic sequence.

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

Obviously Bellman Ford's algorithm solves in O (V.E). Is there a better algorithm?

  • Vote: I like it
  • +19
  • Vote: I do not like it

10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How does Bellman Ford's algorithm solve this? The fact that a circular shift allows a sequence to still satisfy the conditions makes this seem hard...