You are awesome .I viewed almost all videos and its clear my concept , which not being cleared by seeing other videos . Keep posting new videos and this will help us .
Awesome man. You make any algorithms so easy and teaches 3hr things in 15 mins and concept given is very solid. One small thing missed in video.. explanation for time complexity O(E log V)
You do seem to be able to explain things much better than others. Uni is rubbish at explaining things while you have given me at least given me a chance of understanding it. It seems much simpler now you have explained it. Thank you.
If you are still guessing, why the O(E log (v)) complexity, here is an explanation. You visit each edge in this graph at-least once (without which you cannot reach all the vertices). That would be O(E). However, at each edge, you are looking at the priority queue (heap) and doing an extractMin() operation which takes log(n) time in general, for n elements in the heap. Since in the worst case, you will have as many as V elements in the heap, each edge traversal means, a O(log V) time to extractMin from the priority queue(heap). So E times log(v).
@@maksimmartianov5189 The highest degree term is considered in time complexity and hence E will be always >= V, therefore we can say total time complexity as O(E log (v))
@@amurto630 Extract-Min in heap is an operation in which we extract root i.e. min element and then replace it with last level rightmost element and then heapify, so the total time to do this will be O(log V).
I really liked your videos. Can you please upload videos on some of following topics? ->asymtotic complexity -> n queen problem ->travelling salesman problem ->karp-rabin ->strassen matrix multiplication ->randomized algorithms las vegas and monte Carlo ->Amortized analysis ->LC Branch and Bound ->FIFO Branch and Bound ->Multistage Graph ->Flow Shop Scheduling ->binomial heap ->fibbonaci heap
absolutely fantastic explanation! Thank you so much for going through even the most obvious bits as now I have a -rough- idea of how i'm actually going to implement part of my algorithmics C assignment! cheers.
Thanks for the video . I am new for learning in youtube . i felt lot of difference to learn from videos . i have seen many videos recently , yours is fantastic . with code base .
Watched many of your videos, and most of these videos are well explained - good for freshers to computer science, as well as those who want to dust up academics in preparation for new opportunities. Want to commend you on all your great efforts.
I like your videos a lot. This explanation of Dijkstra algorithm is one of the best I've ever seen. Have you ever thinking about make a video of A* algorithm or another search algorithm that uses heuristics? Keep making videos :) Thanks.
Should use D-ary heap instead of Binary heap w/ Dijkstra's algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time
Hi Tushar, Your explanations on the algorithms are brilliant. Have a doubt on extracting minimum value from the map. Why are we extracting minimum value from the map? Picking up any random value/max value from the map will give the same final result. Since for every vertex, we are comparing already found distance and new distance. Only observation I found that using minimum one form the map reduces number of comparisons. Can you please put your thoughts on selecting the minimum one from the map instead of any other value?
+madat brahma I think we extract the minimum because the distance cannot be updated once it has been removed. What I mean is, if you look at his example on the board, D is the last element to get extracted. If it was the second (after the source which is A), then it would be extracted with the distance 9. This is then used to compare other paths with and therefore should not be updated (as any path that relies on D would then have to have their distance updated as well). Extracting the minimum guarantees that all the data in the distance map is the smallest value possible for that vertex. To explain this better, lets say there is a graph of 4 elements ABCD, connected like a square. A is the source, so it is extracted first. It is connected to B and D. Let's say that the edges for AB is 2, BC is 3, CD is 2, and AD is 8. If you extract at random, D could be removed next, making D have a distance set to 8. Then when you eventually extract C, it would be seen that D's distance could be updated to 7, which is less than 8. This isn't a problem at first. But if there were 5 elements, with a node E connected to D but no others, then this would require you to update the distance of E as well, because it is reliant on D's distance. This would introduce another loop of O(v) time every time you update a distance (since you have to check all the nodes that are reliant on that nodes distance). This increases the time complexity since it would occur inside the for loops that are already O(E lg (v)) (I think that's the time complexity, I could be remembering that wrong). By extracting the minimum, it guarantees that anything dependent on that node will not have to have its distance updated once it is extracted.
Why do we need a Min heap ? Can we not store in the Queue instead and have a visited array to keep track of which nodes are visited prior. Although you can modify the distance but do not put back to the queue if it is already visited.
Hi Tushar, I watched many of your algo videos... Many of the concepts are clear now. First of all A BIG THANKS for your videos. In programming part in many videos, you have used Map, LinkedList, Queue and so on. Can you post some videos where programming is done only using Arrays and Objects? Arrays like any array of objects rather using predefined java classes. e.g. int[], Object[], etc. As i need to appear few exams where we can not import any predefined class apart from java.util.Scanner;
Thanks for your nice tutorial. You have mentioned this method inside Vertex class. Can you please describe this method @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + (int) (id ^ (id >>> 32)); return result; }
Hi Tushar, Thank you for your excellent explanation- just as always. I have only one question- how is the space complexity O(E + V) when in all three data structures we only store at most V elements where V is the number of vertices in the graph? This is the only thing I don't understand. Thank you :)
the graph you are searching contains a list of vertices and their edges so I guess the space complexity is just the size of the input data in this case because the other structures are smaller
Hi, Can you make a video explaining the code from the Graph, Vertex and Edge classes that you have in the link you've provided? To be specific, I want to know the significance of the overridden functions that you've written and why they're coded that way. Thanks!
Hey Tushar, we're not just extracting the minimum value but we're also removing it from the map + heap. However, in your video about Prim's, you haven't explained how to remove the minimum value from the data structure. Obviously, if we remove the top element (which is the minimum), the position of all the other elements change and in such a case, how do we update the map (which contains the positions)?
Here's what I did: after removing the element whose index is 0 in the heap (since it would be the lowest value), I am decrementing the index of every other element in the hash map by 1. So the element whose value in the hash map was previously 1, now becomes 0. 2 becomes 1 and so on, which is also what happens to the heap array naturally after we pop out the element at the 0th position. Thank you so much Tushar, my code is working fine, this is the first time I've implemented Dijkstra's algorithm, feels good :) Even though my code is working fine, someone do let me know whether what I did was the correct thing to do. It may be possible that my code breaks in some special cases.
in this vedio u used heap+map to store the information about all the non-evaluated node, but ur implementation is in java, i wanted to know do we have something like that in c++ too, i though of using an array but finding minimum item in it would be O(size of array) and that is a costly affair, hope to get some help.
i had used set and map to implement that, i thought of using priority_queue but at the time i didn't know how to make a min priority_queue in c++(since it is max priority queue by default), although i now know that , anyways thanks
Yes , its his own implementation. Graph ds can be implemented in lot of ways. Check his github github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java
Hi Tushar... Very Well Explained I have implemented the code from scratch after watching your explanation part. github.com/abhishekhandacse/Coding_Java/blob/master/src/geeksforgeeksimproved/graphs/DijkstraAlgorithm.java
#include using namespace std; vector dijkstra(int n,int source, vector G[]) { int INF = (int)1e9; vector D(n, INF); D[source] =0; set Q; Q.insert({0,source}); while(!Q.empty()) { auto top = Q.begin(); int u = top->second; Q.erase(top); for(auto next: G[u]) { int v = next.first; int weight = next.second; if( D[u] + weight < D[v] ) { if(Q.find( {D[v],v})!=Q.end()) Q.erase(Q.find( {D[v], v} )); D[v] = D[u] + weight; Q.insert( {D[v], v} ); } } } return D; } int main(){ int n,m,s,x,y,z; cin>>n>>m>>s; //Input the number of nodes(0 based), number of edges and the source vertex. vector *G=new vector[n]; vectorans; for(int i=0;i>x>>y>>z; //Input the starting vertex of the edge, the ending vertex and the cost of the edge. G[x].push_back(make_pair(y,z)); } ans = dijkstra(n,s,G); //ans has the cost from source to all the vertices. for(int i=0;i
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Aapse acha teacher aaj tak nhi dekha...itna ache se kisi ne nhi smjhaya ye sab...you are really good ❤️❤️
You are awesome .I viewed almost all videos and its clear my concept , which not being cleared by seeing other videos .
Keep posting new videos and this will help us .
bro do these videos help in company placement.does it helped you...
Obviously!! He works at Apple. Hope this answers your question.
Awesome man. You make any algorithms so easy and teaches 3hr things in 15 mins and concept given is very solid. One small thing missed in video.. explanation for time complexity O(E log V)
You do seem to be able to explain things much better than others. Uni is rubbish at explaining things while you have given me at least given me a chance of understanding it.
It seems much simpler now you have explained it. Thank you.
He's awesome
Loved the video. This was a fundamental concept in our Object Oriented 2 class.
He is from my college , Working in Apple
One of the best and simplest videos for understandng dijkastra's algo.. Hats off Tushar... Great work!
I just looked for a video from you about Dijkstra. You're the best teacher I've found in RUclips.
I`m student in korea. Your good explanation Thanks Tushar Roy~
welcome
@@tusharroy2525 Hello MNNITian SIR !!
you helped me in bachelors and need you again in masters god bless you
If you are still guessing, why the O(E log (v)) complexity, here is an explanation. You visit each edge in this graph at-least once (without which you cannot reach all the vertices). That would be O(E). However, at each edge, you are looking at the priority queue (heap) and doing an extractMin() operation which takes log(n) time in general, for n elements in the heap. Since in the worst case, you will have as many as V elements in the heap, each edge traversal means, a O(log V) time to extractMin from the priority queue(heap). So E times log(v).
What about construction of the heap? Isn't it O(v) ?
Isnt extract min operation O(1) while insertion is O(logV)
@@maksimmartianov5189 The highest degree term is considered in time complexity and hence E will be always >= V, therefore we can say total time complexity as O(E log (v))
@@amurto630 Extract-Min in heap is an operation in which we extract root i.e. min element and then replace it with last level rightmost element and then heapify, so the total time to do this will be O(log V).
Thought I will never get an idea till I found this channel 😂
The other videos explaining the algorithm aren't bad, but this is the best one when trying to understand the pseudo code and data structures - thanks!
Dude, these lessons are really simple and easy to grasp.
Thanks a lot, definitely helping me in my quiz tomorrow!! KEEP IT UP! :)
I really liked your videos.
Can you please upload videos on some of following topics?
->asymtotic complexity
-> n queen problem
->travelling salesman problem
->karp-rabin
->strassen matrix multiplication
->randomized algorithms las vegas and monte Carlo
->Amortized analysis
->LC Branch and Bound
->FIFO Branch and Bound
->Multistage Graph
->Flow Shop Scheduling
->binomial heap
->fibbonaci heap
+Tushar Roy thanks
absolutely fantastic explanation! Thank you so much for going through even the most obvious bits as now I have a -rough- idea of how i'm actually going to implement part of my algorithmics C assignment! cheers.
Very nicely explained, especially the complexity part. I could not understand that from other sources. thank you!!
Roy's doing things for global audience, I benefit a lot from his videos as a Chinese student.
Thanks God man. you saved me from quitting learning...
Thanks for the video . I am new for learning in youtube . i felt lot of difference to learn from videos . i have seen many videos recently , yours is fantastic . with code base .
Tushar, thank you so much for your effort. It helps me to understand many things and succesfully take my exams. Thank you!
First Dijkstra's explanation ever that allowed me to visualize the data transformations!
Great video! Thank you so much for your clear explanations and demonstrations.
Your videos are so much better and informative than Siraj ravla's!! Great job!!
Great Video and this channel is my bible for programming questions.
Watched many of your videos, and most of these videos are well explained - good for freshers to computer science, as well as those who want to dust up academics in preparation for new opportunities. Want to commend you on all your great efforts.
your lectures were very helpful me....thanks Tushar for your wonderful videos
dude, your vids are like gold to self-learning coders :) Really appreciate the efforts!
I like your videos a lot. This explanation of Dijkstra algorithm is one of the best I've ever seen.
Have you ever thinking about make a video of A* algorithm or another search algorithm that uses heuristics?
Keep making videos :) Thanks.
Really? I didn't see it. Thanks :)
Thanks man, for keeping it simple and clear unlike others
Excellent, clear explanation. Well-done.
U r not Tushar u r an ultimate solution
HEY I want to thank you, I will forever be grateful if I pass my exams thanks to you! keep it up man!
Well, did you pass? :P
@@sagnik3012 yeah I did xd
You are AWESOME!
Thank you so much God bless you! awesome video! Helped me a lot in understanding this i had struggled a lot with this algo.
One correction at 11:53 we apply extract min V times and decrease key E times. And not both E times.
Great Explanation! Thank you so much Tushar!
Thank you very much, Tushar. Really helpful tips and efficient code.
Should use D-ary heap instead of Binary heap w/ Dijkstra's algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time
Wish I could have viewed these videos earlier I could have been much better in algorithims .Thankyou sir !
Awesome explanation man, you saved me for my final tomorrow :).
Thanks for doing a video on Dijkstra!
So helpful and clear. Thank you so much.
Very nice explanation. Thank you.
thankyou sooo much !!! an IP university student
Nice Video... Please, Put captions above progress bar....
at first i was using dfs to reach all vertex and update but that method was flawed thnx to him i used bfs and got correct ans for each test case
buddy you are soo good AND you explain very well!!
Clear explenation....verry helpful
The legend in explaining and teaching :)
Amazing explanation man .. that will really help me into my project.
greetings ..
Man, i am speechless. Awesome video.
Hi Tushar,
Your explanations on the algorithms are brilliant. Have a doubt on extracting minimum value from the map. Why are we extracting minimum value from the map? Picking up any random value/max value from the map will give the same final result. Since for every vertex, we are comparing already found distance and new distance. Only observation I found that using minimum one form the map reduces number of comparisons. Can you please put your thoughts on selecting the minimum one from the map instead of any other value?
+madat brahma I think we extract the minimum because the distance cannot be updated once it has been removed. What I mean is, if you look at his example on the board, D is the last element to get extracted. If it was the second (after the source which is A), then it would be extracted with the distance 9. This is then used to compare other paths with and therefore should not be updated (as any path that relies on D would then have to have their distance updated as well). Extracting the minimum guarantees that all the data in the distance map is the smallest value possible for that vertex.
To explain this better, lets say there is a graph of 4 elements ABCD, connected like a square. A is the source, so it is extracted first. It is connected to B and D. Let's say that the edges for AB is 2, BC is 3, CD is 2, and AD is 8. If you extract at random, D could be removed next, making D have a distance set to 8. Then when you eventually extract C, it would be seen that D's distance could be updated to 7, which is less than 8. This isn't a problem at first. But if there were 5 elements, with a node E connected to D but no others, then this would require you to update the distance of E as well, because it is reliant on D's distance. This would introduce another loop of O(v) time every time you update a distance (since you have to check all the nodes that are reliant on that nodes distance). This increases the time complexity since it would occur inside the for loops that are already O(E lg (v)) (I think that's the time complexity, I could be remembering that wrong). By extracting the minimum, it guarantees that anything dependent on that node will not have to have its distance updated once it is extracted.
such a clear explanation thank you!!
Why do we need a Min heap ? Can we not store in the Queue instead and have a visited array to keep track of which nodes are visited prior. Although you can modify the distance but do not put back to the queue if it is already visited.
Why the playlist is not in organized manner ?
But the video was awesome :)
Hi Tushar, I watched many of your algo videos... Many of the concepts are clear now.
First of all A BIG THANKS for your videos.
In programming part in many videos, you have used Map, LinkedList, Queue and so on.
Can you post some videos where programming is done only using Arrays and Objects? Arrays like any array of objects rather using predefined java classes. e.g. int[], Object[], etc.
As i need to appear few exams where we can not import any predefined class apart from java.util.Scanner;
Thanks for your nice tutorial. You have mentioned this method inside Vertex class. Can you please describe this method
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (int) (id ^ (id >>> 32));
return result;
}
excellent....good explanation
videos are awesome .
After doing the concept part can you please add complexity of each algorithm?
Complexity for
travelling salesman problem
0/1 Knapsack
optimal BST
N * queen problems
Great videos buddy. Awesome job!
Hi Tushar,
Thank you for your excellent explanation- just as always. I have only one question- how is the space complexity O(E + V) when in all three data structures we only store at most V elements where V is the number of vertices in the graph? This is the only thing I don't understand. Thank you :)
the graph you are searching contains a list of vertices and their edges so I guess the space complexity is just the size of the input data in this case because the other structures are smaller
Hi
Hi,
Can you make a video explaining the code from the Graph, Vertex and Edge classes that you have in the link you've provided? To be specific, I want to know the significance of the overridden functions that you've written and why they're coded that way.
Thanks!
Really good explanation!
love u from iran semnan university
I hardly comment on videos. But man you are awesome. BTW are you IITian?
he is an Apple Engineer
at 8:30 time what would be the value of D in Map+heap table if AD edge have weight
The value of D would be = Weight of edge AD(less than 7)
Hey Tushar, we're not just extracting the minimum value but we're also removing it from the map + heap. However, in your video about Prim's, you haven't explained how to remove the minimum value from the data structure.
Obviously, if we remove the top element (which is the minimum), the position of all the other elements change and in such a case, how do we update the map (which contains the positions)?
Here's what I did: after removing the element whose index is 0 in the heap (since it would be the lowest value), I am decrementing the index of every other element in the hash map by 1.
So the element whose value in the hash map was previously 1, now becomes 0. 2 becomes 1 and so on, which is also what happens to the heap array naturally after we pop out the element at the 0th position.
Thank you so much Tushar, my code is working fine, this is the first time I've implemented Dijkstra's algorithm, feels good :)
Even though my code is working fine, someone do let me know whether what I did was the correct thing to do. It may be possible that my code breaks in some special cases.
Genius you helped me find the error
u r excellent..Its helping ..
awesome man, u r really helpful
@1:30 "The link to that video is also attached in this video here"
No it's not. What is a heap? I don't know
google Priority Queue
Hello @Tushar Roy why are we not using java.util.PriorityQueue and instead our own version using BinaryMinHeap? can someone explain?
How to find w when both value are same... Which one should be considered as minimum?
Thanks, this helped me a lot !
Great explanation..
is Dijkstra's algo, a greedy method or dynamic or both?
very well explained..
can we use priority queue of java.util package in place of our min heap ??
Perfect as always..!
Your videos are top!
in this vedio u used heap+map to store the information about all the non-evaluated node, but ur implementation is in java, i wanted to know do we have something like that in c++ too, i though of using an array but finding minimum item in it would be O(size of array) and that is a costly affair,
hope to get some help.
i had used set and map to implement that, i thought of using priority_queue but at the time i didn't know how to make a min priority_queue in c++(since it is max priority queue by default), although i now know that , anyways thanks
Excellent explanation!
how can we update the distances, once the variable is sent in priority queue?
I think the easiest way is to remove the element and insert a new one.
Vertex class not found in your java Dijkstra’ code.. how to fix this?
Gourav Goyal it is declared in Graph class as inner class
anyone know where the Vertex class came from in his code? I'm assuming its his own implementation
Yes , its his own implementation. Graph ds can be implemented in lot of ways. Check his github github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java
why didn't you just use set, or priorityQueue and prefer Heap and Map together
Where is the link for graph class?
Bro your voice tore my ear drums, but aside from that good tutorial!
WHY WHY in The world when a programmer is born he says "Hello World" :)
Awesome Video
nice
Great work
god bless your soul
You got the time complexity wrong. According to Fredman & Tarjan (1984), it should be O(E + V*log(V)) .
Hi Tushar... Very Well Explained
I have implemented the code from scratch after watching your explanation part.
github.com/abhishekhandacse/Coding_Java/blob/master/src/geeksforgeeksimproved/graphs/DijkstraAlgorithm.java
what is vertex class here
how you build heap + map data structure. Can anyone explain
awesome, thanks a lot
Thank you.sir.
well explained (y)
You are awesome! Please share the codes in C++ too.
#include
using namespace std;
vector dijkstra(int n,int source, vector G[]) {
int INF = (int)1e9;
vector D(n, INF);
D[source] =0;
set Q;
Q.insert({0,source});
while(!Q.empty()) {
auto top = Q.begin();
int u = top->second;
Q.erase(top);
for(auto next: G[u]) {
int v = next.first;
int weight = next.second;
if( D[u] + weight < D[v] ) {
if(Q.find( {D[v],v})!=Q.end())
Q.erase(Q.find( {D[v], v} ));
D[v] = D[u] + weight;
Q.insert( {D[v], v} );
}
}
}
return D;
}
int main(){
int n,m,s,x,y,z;
cin>>n>>m>>s;
//Input the number of nodes(0 based), number of edges and the source vertex.
vector *G=new vector[n];
vectorans;
for(int i=0;i>x>>y>>z;
//Input the starting vertex of the edge, the ending vertex and the cost of the edge.
G[x].push_back(make_pair(y,z));
}
ans = dijkstra(n,s,G); //ans has the cost from source to all the vertices.
for(int i=0;i