Cheap and Secure Web Hosting Provider : See Now

[Solved]: Transforming the sorting problem into Dijkstra

, , No Comments
Problem Detail: 

To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem.

I know you need to do create a graph based on the numeric values and that Dijkstra will traverse it in order, any help with the rest and how to evaluate it? Thank you.

Asked By : user21996

Answered By : Yuval Filmus

What you want is to reduce sorting (or element uniqueness) to the single source shortest path problem (rather than to Dijkstra's particular algorithm!) using an $o(n\log n)$ time reduction whose output has size $O(n)$. Then you will get a tight decision tree lower bound in the algebraic decision tree model for constant degree (Dijkstra's algorithm can be implemented using a linear algebraic decision tree).

Such a reduction is probably not known. See for example D.W.'s question on cstheory.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback