# Transforming the sorting problem into Dijkstra [closed]

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.

• What are the resource constraints? – Raphael Dec 15 '14 at 15:25
• Could you clarify what you're trying to do? Your question is difficult to understand. Do you want to prove the minimal complexity of the shortest path problem, or do I completely misunderstand? – Gilles 'SO- stop being evil' Dec 15 '14 at 15:26

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