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.
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"
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
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)
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
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
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.
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.
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.
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.
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
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.
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😊
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".
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.
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!!!
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....
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!!
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
Bro ne pura phd kar diya Time Complexity pe 😂.
Thanks bhai for such a nice explanation.
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.
habibi tum time complexity mast samjai ho ....hum khush hui ..tum accha kaam karti
this is a type of content that I would not give a second thought for even paying for it
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"
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)
immense amount of efforts put in by you!! hats -off raj bhaiya.
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)
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
The effort you have put are shown clearly in this video !
Great explanations.
striver bhai, you will become a person which will be remembered in history forever.😊
this is the top 1 rating video from my perspective for understanding of working flow time complexity throughout the code.
brother u nailed it>>>>> RESPECT
This is the best explanation I have ever seen in my life. Thanks Striver :)
Amazing explanation of the derivation .I have never seen any TH-camr going into such a deep concept..
you are the best youtuber in the world for coding ♥♥♥♥♥♥
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
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
One of the best time complexity analysis explanation, thank 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😘
Kya padhaya hain bhyii 🔥🔥🔥🔥🔥🔥🔥 aag ekdum
Finally after days! We were awaiting for the new videos in the Graph playlist! Thank you so much for your immense efforts, 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)
}
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.
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
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.
Best Explaination of Time complexity!✨
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
Striver, Shiv Baba Bless you , you are like God's swarup
Time complexity explanation is the best! Thanks!
What an Explanation man hat's off to you 🤯🤯🤯
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
TC explanation was on another level
understood, thanks for the awesome derivation of the time complexity
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
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.
explanation of time complexity perfect
thank you so much
really love your explanations
One of the best videos of Dijkstra's Algorithm on the internet.
The derivation was marvelous
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
God level explanantion
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.
sir the time complexity explanation was very good. thank you :)
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
Awesome derivation, Hats off
Time Complexity explanation was awesome
Thank you so much for this amazing explanation Raj
JUST MINDBLOWING!!! Thanks a ton!!!!
Wonderful Explanation!!
Understood! Wooow! Super fantastic explanation as always, thank you very much!!
the explanation of T.C. is OP .
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😊
Very very very nice explanation....
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".
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
Mastering Graph ❤️🙌🏻
Understood. Thank you so much.
Hey striver I have understood the time complexity very well can you please explain time complexity of bfs and dfs once🙂🙂
Understood. Thanks for all the effort.👌
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
Understood.
Thank you Striver!
After watching this video I came to realize why striver is the goat..🐐🐐
commedable job once again striver!!!
fully understood. Thx a lot
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.
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!!!
Thank you very much. You are a genius.
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....
Great Explanation ❤
Amazing explaination
wonderfull explanation sir
Striver U are just Op..❤❤❤🙏
Much needed Awesome explanation !!!!
Amazing Explanation.
bhai content hai maja aagya ✨✨✨✨
This is really good❤❤❤❤❤❤
great explanation 😇
Dedication level op 🔥
very nice explanation
Amazing explanation sir
Amazing Explanation Bhaiya
understood sir...amazing one
Best explanation
Understood Sir, Thank you very much
very indepth explaintion
Bhaiya Bharat Ratna is waiting for you ..
burrapadu explanation guru
understood sir,
thanks for making this video sir 🩷
It is a complete graph where every node is connected to every other nodes of the graph or in other words the degree of each node is v-1
Great work !!
understood striver bhai
Thank you sir ☺️
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...
Boossssssssssssssss❤ this is called quality education