### -200's blog

By -200, history, 3 weeks ago,

What is purpose of using priority queue in dijkstra algorithm?? In leetcode i solved a problem which requires dijkstra algo,I implemented it by using normal queue and my solution got accepted but when I'm solving CF problem related to dijkstra I got TLE because of using queue [https://codeforces.com/contest/20/submission/266533020] After that I use priority queue and my solution is accepted [https://codeforces.com/contest/20/submission/266536259] can anyone explain what is the reason??

• +3

 » 3 weeks ago, # | ← Rev. 2 →   0 A queue is a first-in-first-out data structure — so basically, you insert elements in O(1), and then when you retrieve the elements, you get them back O(1) in the order that you inserted them. For example, in some pseudocode notation: q = [] q.push(5) -> [5] q.push(10) -> [5, 10] q.push(15) -> [5, 10, 15] q.pop() -> [10, 15] (because the five was inserted first, it is retrieved first) q.pop() -> [15] (you get the idea I hope) A priority queue, on the other hand, allows you to insert elements in O(logn), but then the pop method is different — it retrieves the smallest elementfor example: pq = [] pq.push(4) pq.push(3) pq.push(1) pq.push(5) pq.push(8) -> now the pq contains elements {4, 3, 1, 5, 8} pq.pop() will return 1, because 1 is the smallest element pq.pop() the second time will return 3 pq.pop() -> 4 pq.pop() -> 5 pq.pop() -> 8 Hope this helps, if you have any more questions just let me know
•  » » 3 weeks ago, # ^ |   +5 Yes bro you are correct but that is not my question.I'm asking what is the significance of using priority queue over queue in dijkstra algo. Anyway we need to visit all the path's right?? So why we use priority queue.I you still didn't got my doubt just take a random leetcode problem which requires dijkstra algo and submit it by using normal queue.You'll get AC.
•  » » » 3 weeks ago, # ^ |   +4 But the whole point of Dijkstra's is that it's a greedy algorithm — at every iteration, you take the node with the shortest distance then update the neighbours. How would you even do it with a queue? That would require lots and lots more iterations.
 » 3 weeks ago, # | ← Rev. 2 →   +5 i had the same problem too for solving 20C - Dijkstra?, the normal dijkstra gets TLE on test 28. its because the order of the priority queue approach(if i am correct) is $O(E log V)$ but the other approach is $O(V^2)$, if you want to know why:the priority queue approach: Each time a new vertex is added to the priority queue, or an existing vertex's distance is updated, the priority queue is rearranged, which takes $O(log V)$ time. The total number of times the priority queue is accessed (push, pop, or update) is proportional to the number of edges, which is $O(E)$.the other approach: At each step, the algorithm must search through the entire set of unprocessed vertices to find the vertex with the shortest distance, which takes $O(V)$ time. The algorithm then updates the distances of all the neighbors of the selected vertex, which takes $O(V)$ time as well.
•  » » 3 weeks ago, # ^ |   0 Oh! Thank you bro
•  » » 3 weeks ago, # ^ |   0 Strictly speaking, the optimized one is $O((E+V)\log V)$. You can't throw away the $V\log V$ term though it always satisfies $E>V$ for a connected graph.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 thanks for completing it.
 » 3 weeks ago, # |   0 who has a name like -200? What does it even mean?