1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are the resource constraints? $\endgroup$ – Raphael Dec 15 '14 at 15:25
  • $\begingroup$ 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? $\endgroup$ – Gilles 'SO- stop being evil' Dec 15 '14 at 15:26
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.