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
Understood! Wow, your mathematical deductive reasoning was very sound & easily followed! I appreciate the step by step analysis w/o skipping over any steps. 🙌
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.
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.
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
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
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♥
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"
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.
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)
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
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
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) }
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"
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.
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
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.
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".
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.
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....
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.
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😊
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.
AMAZING TIME COMPLEXITY EXPLANATIONNN!!! I wrote everything downn!! I have one question though please. I didn't get how you converted V^2 to E. (V-1) which is Edges * V which is Vertices = V^2. So how can E*V = E? I think I missed something. If anyone would be willing to explain please? AS USUAL, UNBEATABLE WORK STRIVER!! Thx for the amazing efforts!!!
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?
Great Video. Thanks. But I am a bit confused. If the heap size could go upto V^2, why are we considering the complexity for the main loop (while(!PQ.empty)) as O(V)? And according to this logic, wouldn't a normal queue have better time complexity in any case, since we are saving the PQ dequeue & enqueue operations there (2 * log(V^2))?
I think in PQ we are considering worst case TC and according to that I think both Q and PQ would be the same TC, but the thing is PQ calculates shortest paths first. Maybe.
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.
Bhaya,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.
I have doubt . they said in worst case we will have v*(v-1) entries in queue, but how is it possible? for example if we take 4 node graph and starting with zero . lets consider whenn we pop out node zero from queue , and remaining 3 nodes pushed into queue. now when next node will be popped out there is no way it will push 0(parent of it ) . At most it will be able to push the remaining 2 nodes right?
yes you are right,but for a larger number the queue will be definitely much greater than V and some what lesser than v*v ,so he done the approximation to v*v
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...
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
Dil me baste ho tum yr ♥️ humare
Understood! Wow, your mathematical deductive reasoning was very sound & easily followed!
I appreciate the step by step analysis w/o skipping over any steps. 🙌
can you solve skiplist problem on leetcode
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.
understood!!
Bro ne pura phd kar diya Time Complexity pe 😂.
Thanks bhai for such a nice explanation.
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.
indeed
True❤
true
Bhaiya you deserve Bharat Ratna for this quality content.
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
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
@@janedoe1721 im not able to understand how v2=E. can you explain?
@@vaisakh5802 in densest graph there will be V nodes and each of them connected to V-1 nodes => total edges=v*v-1
@@vaisakh5802 IT Would be v2 = 2*Edges= (aprrox=E)
this is a type of content that I would not give a second thought for even paying for it
habibi tum time complexity mast samjai ho ....hum khush hui ..tum accha kaam karti
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.
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♥
in T.C , at starting it's looking impossible that it reaches to Elog(V) to me , but as video ends , it clears my mind thanx striver😘
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"
brother u nailed it>>>>> RESPECT
striver bhai, you will become a person which will be remembered in history forever.😊
immense amount of efforts put in by you!! hats -off raj bhaiya.
The explanation of the time complexity is just amazing! Thank you so much!
Seriously ,you are the best. The deep work you did to become skillful is inspirational
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.
One of the best time complexity analysis explanation, thank you !! 🙏
this is the top 1 rating video from my perspective for understanding of working flow time complexity throughout the code.
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)
Amazing explanation of the derivation .I have never seen any RUclipsr going into such a deep concept..
This is the best explanation I have ever seen in my life. Thanks Striver :)
Striver, Shiv Baba Bless you , you are like God's swarup
you are the best youtuber in the world for coding ♥♥♥♥♥♥
Best Explaination of Time complexity!✨
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
The effort you have put are shown clearly in this video !
Great explanations.
Time complexity explanation is the best! Thanks!
understood, thanks for the awesome derivation of the time complexity
explanation of time complexity perfect
thank you so much
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
What an Explanation man hat's off to you 🤯🤯🤯
Kya padhaya hain bhyii 🔥🔥🔥🔥🔥🔥🔥 aag ekdum
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)
}
correct bro
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"
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.
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
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.
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".
The derivation was marvelous
TC explanation was on another level
Finally after days! We were awaiting for the new videos in the Graph playlist! Thank you so much for your immense efforts, Striver.
Awesome derivation, Hats off
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
JUST MINDBLOWING!!! Thanks a ton!!!!
Thank you so much for this amazing explanation Raj
sir the time complexity explanation was very good. thank you :)
Wonderful Explanation!!
Very very very nice explanation....
really love your explanations
the explanation of T.C. is OP .
After watching this video I came to realize why striver is the goat..🐐🐐
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
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.
commedable job once again striver!!!
One of the best videos of Dijkstra's Algorithm on the internet.
Understood. Thanks for all the effort.👌
Understood.
Thank you Striver!
Understood. Thank you so much.
Time Complexity explanation was awesome
Mastering Graph ❤️🙌🏻
God level explanantion
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....
Understood! Wooow! Super fantastic explanation as always, thank you very much!!
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.
wonderfull explanation sir
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😊
Thank you very much. You are a genius.
fully understood. Thx a lot
Striver U are just Op..❤❤❤🙏
Much needed Awesome explanation !!!!
Great Explanation ❤
understood all 3 videos. time complexity part was awesome
Amazing explaination
Amazing Explanation.
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.
I'm also stuck at this point. please reply if you got this clear.
same doubt
understood sir,
thanks for making this video sir 🩷
very nice explanation
understood sir...amazing one
AMAZING TIME COMPLEXITY EXPLANATIONNN!!! I wrote everything downn!!
I have one question though please. I didn't get how you converted V^2 to E. (V-1) which is Edges * V which is Vertices = V^2. So how can E*V = E? I think I missed something. If anyone would be willing to explain please?
AS USUAL, UNBEATABLE WORK STRIVER!! Thx for the amazing efforts!!!
Amazing explanation sir
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?
I too got the same doubt.
Understood Sir, Thank you very much
Great Video. Thanks.
But I am a bit confused. If the heap size could go upto V^2, why are we considering the complexity for the main loop (while(!PQ.empty)) as O(V)? And according to this logic, wouldn't a normal queue have better time complexity in any case, since we are saving the PQ dequeue & enqueue operations there (2 * log(V^2))?
I think in PQ we are considering worst case TC and according to that I think both Q and PQ would be the same TC, but the thing is PQ calculates shortest paths first. Maybe.
@@tasneemayham974 At the end PQ and Q both do the same number of iteration only difference is that, PQ choose the smallest distance first to traverse
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.
same doubt
Sir it was awesome but there is a doubt in taking pq as O(V) time and taking time of heap.size as O(V^2). Please reply .
same doubt
Bhaya,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.
Hey striver I have understood the time complexity very well can you please explain time complexity of bfs and dfs once🙂🙂
very indepth explaintion
This is really good❤❤❤❤❤❤
Bhaiya Bharat Ratna is waiting for you ..
Amazing Explanation Bhaiya
bhai content hai maja aagya ✨✨✨✨
understood striver bhai
great explanation 😇
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?
yeah I also think same there is a mistake in this
Dedication level op 🔥
Best explanation
Boossssssssssssssss❤ this is called quality education
I have doubt . they said in worst case we will have v*(v-1) entries in queue, but how is it possible? for example if we take 4 node graph and starting with zero . lets consider whenn we pop out node zero from queue , and remaining 3 nodes pushed into queue. now when next node will be popped out there is no way it will push 0(parent of it ) . At most it will be able to push the remaining 2 nodes right?
yes you are right,but for a larger number the queue will be definitely much greater than V and some what lesser than v*v ,so he done the approximation to v*v
burrapadu explanation guru
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...
Great work !!
you are always amazing man!!