3
$\begingroup$

I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm.

Is a priority queue a possible data structure? Will running Dijkstra's algorithm using a priority queue reduce or increase the complexity? Will I overshoot the problem?

$\endgroup$
  • $\begingroup$ What would the priority queue keep track of? What are its contents? $\endgroup$ – Hendrik Jan Sep 24 '16 at 11:02
  • $\begingroup$ Any data structure? What happens if you use a stack or a queue? $\endgroup$ – Raphael Sep 24 '16 at 13:30
  • 3
    $\begingroup$ "I do not see any implementation details of dijkstra's algorithm" -- check other sources, then. $\endgroup$ – Raphael Sep 24 '16 at 13:30
  • 1
    $\begingroup$ I have found this document very useful for working with the A* algorithm (which is very closely related to Dijkstra's algorithm). It contains a very good discussion on the tradeoffs involved in using different data structures to represent sets, and AFAICS a large proportion of its discussion should apply to Dijkstra's algorithm as much as it does to A*. $\endgroup$ – Periata Breatta Sep 24 '16 at 15:23
7
$\begingroup$

Yes, you can use priority queues to improve the complexity of the algorithm from $O(V^2)$ to $O(|E| + |V| \log|V|)$ where $E$ is the number of edges and $V$ is the number of nodes.

You should consider carefully the number of nodes in your graph and the desired run time before adding complexity to your implementation.

See here for a brief explanation of performance vs difficulty trade offs.

To summarize the blog, using a regular queue can still speed up Dijkstra's algorithm by up to a factor of 4 in most cases, with rarely occurring graphs running in $O(V^3)$. The link says "never" occurring, but that would depend on the actual problem you are solving.

See this for the original research on using min-priority queues to speed up Dijkstra's algorithm, it is the fastest known implementation for Dijkstra's algorithm.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Sep 24 '16 at 14:52
  • $\begingroup$ Also, you can improve your answer by giving a summary of that blog post. The link may go dead at any point in time, which would make your answer that much less useful. $\endgroup$ – Raphael Sep 24 '16 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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