# Can I run Dijkstra's algorithm using priority queue?

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?

• What would the priority queue keep track of? What are its contents? – Hendrik Jan Sep 24 '16 at 11:02
• Any data structure? What happens if you use a stack or a queue? – Raphael Sep 24 '16 at 13:30
• "I do not see any implementation details of dijkstra's algorithm" -- check other sources, then. – Raphael Sep 24 '16 at 13:30
• 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*. – Periata Breatta Sep 24 '16 at 15:23

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