G-34. Dijkstra's Algorithm - Why PQ and not Q, Intuition, Time Complexity Derivation - Part 3

Disclaimer: Please watch Part-1 and Part-2
Part-1: • G-32. Dijkstra's Algor...
Part-2: • G-33. Dijkstra's Algor...
GfG-Problem Link: bit.ly/3KeZZ7j
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@unknown-cj8gv]

Dil me baste ho tum yr ♥️ humare

[@raysdev]

Understood! Wow, your mathematical deductive reasoning was very sound & easily followed! I appreciate the step by step analysis w/o skipping over any steps. 🙌

[@rushikeshpol5844]

can you solve skiplist problem on leetcode

[@deviprasad_bal]

At any time, a heap can't have same vertex twice, then the heapsize must be log(V) instead of log(V^2). therefore, the maximum heap size can be equal to the number of vertices in the graph, V, and not V^2. Please correct me if I am wrong.

[@priyanshkumar17]

understood!!

[@yatendraupadhyay2180]

Bhaiya you deserve Bharat Ratna for this quality content.

[@ishanshah3309]

this TC explanation is brilliant. have never seen such an amazing video of calculating Time complexity. This Graph series I've seen so far is definitely the best (I bet even any paid course wont be able to beat it ) and is on another level.

[@piyushsaxena6243]

indeed

[@ankitjha9862]

True❤

[@priyanshkumar17]

true

[@JayPatel-sn7it]

Bro ne pura phd kar diya Time Complexity pe 😂. Thanks bhai for such a nice explanation.

[@darkstudio3170]

Guys many of you having doubt that heap size is worst case V2 then while loop should also run V2 times. First of all, the assumption taken that Max Heap Size will be in worst case V2 is itself is wrong . Adding V2 node in any case is not possible. You can dry run , you will find that the distance condition wont allow V2 node to the queue in any case possible + the every node we will processed (pQ.poll()) wont be added to the queue again (you can marked those node vis also , wont have any effect on ans), In worst case heap size can go nV where nELogV. Period

[@janedoe1721]

I agree, the only difference I think is that a node at max will have V-1 edges, not E. so, V(logV + (V-1).logV) = V^2.logV=ElogV. Let me know if this makes sense

[@vaisakh5802]

@@janedoe1721 im not able to understand how v2=E. can you explain?

[@jotsinghbindra8317]

@@vaisakh5802 in densest graph there will be V nodes and each of them connected to V-1 nodes => total edges=v*v-1

[@codinghustler6771]

I Understood this by your previous graph series. But from this it just make everything clear. Thank you Raj bhaiya for all of your effort.

[@CodeMode9313]

habibi tum time complexity mast samjai ho ....hum khush hui ..tum accha kaam karti

[@ntsequalifier341]

I loved the way u said hit that like button you really work good. I mean u have upgraded the level of DSA taught by any Indian teacher.

[@abdulqadirboxwala5414]

this is a type of content that I would not give a second thought for even paying for it

[@user-in2oy4zj2h]

immense amount of efforts put in by you!! hats -off raj bhaiya.

[@amantripathi4100]

brother u nailed it>>>>> RESPECT

[@adityan5302]

I suspect that you're the creator of these Data Structures bro.... Just simply amazing... Love u bro. I succeded in one of the interviews because of u. This is because of you♥

[@sunny_23561]

This video just blew my mind.... Huge thanks Raj bhaiya... Now I am really willing to spend next 2-3 hours to concrete all the concepts on my own regarding this Dijkstra's Algo and shortest path.... "UNDERSTOOD"

[@ranjeet_sohanpal]

Seriously ,you are the best. The deep work you did to become skillful is inspirational

[@aadharjain313]

those who cannot understand or digest why TC is O(ElogE) for priority queue and O(ElogV) for set. Think in this manner that for priority queue , there is no way we can erase duplicate or recurring nodes, so in worst case heap will be having V*(V-1) nodes i.e = E . and hence "logE" for set method, we will be erasing the node from the set first before inserting it with a better distance, that means even in worst case , we won't be having duplicate nodes. hence, at worst (hypothetically) all vertices can be present in the set (but no single vertex will be present twice) . hence maximum heap size boils down to "V'. that is why "log V".

[@ekanshlohiya98]

If the outer loop is running while the heap is not empty then it will also run for the size of heap times i.e., O(v2). I think one optimization is possible here. maintain the count of visited nodes say ct and as soon as the ct becomes n, just break from the priority queue. Now we know, that priority queue picks only least cost path for the node, so mark it as visited since the least cost for that node is already done and increase the count of visited nodes. So, as soon as shortest path for all nodes is calculated from priority queue, the entries which are not optimal will not need to be popped out and we will save the extra time. vector dijkstra(int n, vector adj[], int src) { priority_queue pq; vector dist(n,INT_MAX); dist[src] = 0; pq.push({0,src}); int ct = 0; vector vis(n,0); // vis[src]=1; while(!pq.empty()) //o(v) { if(ct==n) break; auto d = pq.top().first; auto node = pq.top().second; pq.pop(); //log(heap size) -> log(v2) //worst case heap size O(v2) //everyone is connected to every other one so v-1 edges for v nodes each if(vis[node]) continue; vis[node]=1; ct++; for(auto it:adj[node]) //o(v-1) { int u = node; int v = it[0]; int wt = it[1]; if(!vis[v] and dist[v]>dist[u]+wt) { dist[v] = dist[u] + wt; pq.push({dist[v],v}); //log(v2) } } } return dist; //O(v * (log(v2)+(v-1)(log(v2)))) //O(v * log(v2)*(v)) //O(v2 log(v2)) //O(2 v2logv) //O(ElogV) }

[@spydycoder6668]

correct bro

[@gouravgarg1069]

if its so,why we need to check and update for same node again again i think pq picks "node with least cost from source" not "least cost path for the node"

[@anmoljain8327]

I also had the same doubt, that if we will allow the loop to run till priority_queue becomes empty then, the normal queue and priority_queue will take the same time. you found the solution.

[@darkstudio3170]

this wont work , you correct about the time complexity part though . The thing you may have V2 node in queue but not all of them will be processed hence V2 wont be multiplied to inner part . In generall in it is fair to say that nV node will be process where n

[@prathyush6508]

You're right bro, but if that is the case then priority queue should be faster than set as we are still doing the same thing as set but not removing any elements.

[@algorithmsbyaditi]

You explained it really well ! I tried to understand it by reading a lot of blogs and discussions but was not able to but got your explanation. Thank you for this great great video.

[@mdyousufgazi4030]

amazing. i really appreciate it how you explained the whole dijktra's algorithm. and the last part where you showed the the time complexity is O(E log V)

[@bageshwardham-1M]

GUYs please dont compare love and striver. Both are great on their own •meko graph striver se padhna psnd hai •aur trees love babbar ka aisa hi kuch scene boht logo ka hoga... To jisko jiska smjh aata hai usse padho...koi dakka mukki ni😊

[@top_g755]

We take PQ instead of q to reduce no. Traversal (unnecessary) using PQ what we do is in initial traversal we used to choose the minimum one

[@nikhilkrishna643]

The explanation of the time complexity is just amazing! Thank you so much!

[@rpdesigns3545]

I think the time complexity with queue will be same as of the priority queue just take the queueq and instead taking distance from the pair take it from the distance matrix. for the eg u took we will have node 3 twice in the queue and the distance matrix will have min distance of 3 to node 3. And we will calculate the distance to node 4 and 5 and pop and now when we will come to the next node 3 in queue the condition distance[node 3]+edgewt of 5

[@Ritik_Mangal]

striver bhai, you will become a person which will be remembered in history forever.😊

[@arjunju469]

God level explanantion

[@parvmunjal7986]

This is the best explanation I have ever seen in my life. Thanks Striver :)

[@niteshverma8281]

you are the best youtuber in the world for coding ♥♥♥♥♥♥

[@adityagandhi4712]

The effort you have put are shown clearly in this video ! Great explanations.

[@UCSSaloni]

00:00 Explaining Dijkstra's algorithm and why priority queue is used 01:58 Using a priority queue can save time in pathfinding 03:47 Optimize distance calculation by using minimal distance 05:40 Using priority queue to reach minimal nodes first reduces unnecessary exploration of parts. 07:25 The while loop runs for V, which is the total number of nodes. 09:16 Optimizing priority queue operations in graph algorithms 11:12 Pushing nodes in worst-case scenario results in V^2 Heap size 12:59 Explaining the time complexity of Dijkstra's algorithm Crafted by Merlin AI.

[@sambhavagarwal5871]

understood all 3 videos. amazing striver this graph Series is best in the best as well as paid courses Please upload more videos if its there thanks a lot striver

[@chirayusanghvi8885]

One of the best time complexity analysis explanation, thank you !! 🙏

[@g51661]

Bhaiya, I have one doubt. If we're taking Heap size = V^2 appx. then while loop will also run for V^2 times, no? So, jo humne V assume kia hai doesn't that contradict with later heap size?

[@abhilash6661]

I too got the same doubt.

[@user-lw9dj8we7k]

this is the top 1 rating video from my perspective for understanding of working flow time complexity throughout the code.

[@amanasrani6405]

Striver, Shiv Baba Bless you , you are like God's swarup

[@avi7629]

Kya padhaya hain bhyii 🔥🔥🔥🔥🔥🔥🔥 aag ekdum

[@visase2036]

Finally after days! We were awaiting for the new videos in the Graph playlist! Thank you so much for your immense efforts, Striver.

[@piyushk_071]

Best Explaination of Time complexity!✨

[@nishanthazarikab9166]

Amazing explanation of the derivation .I have never seen any KZbinr going into such a deep concept..

[@shreyarawatvlogs6920]

JUST MINDBLOWING!!! Thanks a ton!!!!

[@tanya8353]

Wonderful Explanation!!

[@UECAshutoshKumar]

Thank you sir ☺️

[@vijethkashyap151]

Time complexity explanation is the best! Thanks!

[@satraprathore5349]

Awesome derivation, Hats off

[@Nirala_414]

Mastering Graph ❤️🙌🏻

[@gauristar4094]

commedable job once again striver!!!

[@RahulSharma-ht2xz]

TC explanation was on another level

[@shigoeditz7079]

What an Explanation man hat's off to you 🤯🤯🤯

[@Kokowangmini]

Understood. Thank you so much.

[@shivamgupta-ch8kw]

Hey, If we have taken the heap size as V^2 then the while( !pq.empty()) this loop should also run for V^2 times, not V. Please correct me If I am wrong.

[@akshaykumardwivedi]

I'm also stuck at this point. please reply if you got this clear.

[@TheRandomPerson49]

same doubt

[@mightygerman]

Very very very nice explanation....

[@piyushsaxena6243]

really love your explanations

[@BiswajitDas__0]

Amazing Explanation.

[@user-cl9cn5xu4e]

Boossssssssssssssss❤ this is called quality education

[@yaswanthkosuru]

This is really good❤❤❤❤❤❤

[@harshkilaji]

The derivation was marvelous

[@cinime]

Understood! Wooow! Super fantastic explanation as always, thank you very much!!

[@prathamkapoor2513]

Time Complexity explanation was awesome

[@athangkulkarni8245]

Understood. Thank you Striver!

[@rohitn6333]

sir the time complexity explanation was very good. thank you :)

[@parvahuja7618]

very indepth explaintion

[@KapilMaan-vw9sd]

understood sir, thanks for making this video sir 🩷

[@garimakumari4346]

thanku understood😁

[@prithvisen6560]

Great Explanation ❤

[@priyanshajmera3177]

number of edges in worst case will be n*(n-1)/2 please check it in last segment of video . But Great lecture By the way

[@user-tl5cs7dx1c]

wonderfull explanation sir

[@piyushjaiswal9192]

One of the best videos of Dijkstra's Algorithm on the internet.

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@snvlogger4169]

the explanation of T.C. is OP .

[@aasifali9139]

fully understood. Thx a lot

[@karthikavijayannv5319]

Understood

[@meetkgp]

I want to ask a question regarding the time complexity derivation. It seems that during the process, V^2 was substituted with E. However, in the case of a tree graph or sparse graph, where our scenario aligns, O(V) is equivalent to O(E). Therefore, it would be considered incorrect to substitute V^2 with E in this particular situation.

[@hemachel175]

Understood. Thanks for all the effort.👌

[@user-kl3qv1sc8k]

Amazing explaination

[@codingisfun-pranayharishch3001]

Amazing explanation sir

[@NiveditaKar-xj6ew]

Thank you so much for this amazing explanation Raj

[@user-km8en8ym1h]

Best explanation

[@user-dg7pu8oo6v]

My mind is fucking blown right now i never ever thought I will ever be able to understand anything like this........ Thank you very very much you are a god for me bro...

[@abhijeetbasfore6816]

understood all 3 videos. time complexity part was awesome

[@manishadodeja2014]

if heap here is the priority queue and if heap size is v^2 then the complexity for while(pq is not empty) should also be v^2 and not v right?

[@visheshagrawal8676]

yeah I also think same there is a mistake in this

[@user-fs8km9qc8f]

very nice explanation

[@lakshaysharma852]

Much needed Awesome explanation !!!!

[@arsalanahmed6480]

shukriya

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@saibunny1253]

understood striver bhai

[@mahirneema136]

great explanation 😇

[@yatendraupadhyay2180]

Bhaiya Bharat Ratna is waiting for you ..

[@itz_me_imraan02]

It got clear now...i was wondering the same dat even Queue gives the same answer...understood now dat it gets TLE due to too many unnecessary paths calculations....

[@ShivamKumar-zn4uc]

After watching this video I came to realize why striver is the goat..🐐🐐

[@GhostVaibhav]

Understood🔥

[@VISHALMISHRA-ff2ih]

Although (3,3) wiil be at top we will also inserting the element in the Priority_queue like (7,3) and (3,3) both then the Node 3 is traversed two times..then how the complexity reduces in Priority queue only thing is better that the minm we will get everytime.

[@TheRandomPerson49]

same doubt

[@abhinandansingh1922]

can anyone tell me why the outer loop is O(V) and not O(V^2) ?

[@shivamgupta-ch8kw]

Same doubt

[@avi7629]

Dedication level op 🔥

[@tasneemayham974]

SPECTACULARRRRRRR!!!!

[@AJ-xc3ks]

Striver U are just Op..❤❤❤🙏

[@poojithkumar2283]

Hey striver I have understood the time complexity very well can you please explain time complexity of bfs and dfs once🙂🙂

[@namamiNarayana]

Understood! :) Thank you for your invaluable efforts striver! _/\_ ^^

[@manojnavinjamuri5867]

understood

[@evilpollination1916]

Understood.

[@RapartiChaitanya]

Branch and Bounding!

[@visheshagrawal8676]

bhai content hai maja aagya ✨✨✨✨

[@shyamalaravind5906]

Understood!