World's most popular travel blog for travel bloggers.

# [Solved]: Transforming the sorting problem into Dijkstra

, ,
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.

#### 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 : http://cs.stackexchange.com/questions/35206

3.2K people like this