How to use Dijkstra's Algorithm with Code
Вставка
- Опубліковано 25 сер 2024
- This is a tutorial on the Dijkstra's algorithm, also known as the single source shortest path algorithm. It is extensively used to solve graph problems. We use an example to understand the algorithm and then walk through the the code.
Dijkstra's uses both concepts of Greedy(Finding the next city to pick), and DP(using previously calculated distances).
Code:
algs4.cs.princ...
References:
www.geeksforgee...
web.engr.orego...
math.mit.edu/~r...
The most beautiful part about you that you know the real struggle of a student and you focus on that part specially XD Thank you for the tutorial
Thanks Sunny!
Sir can you make a tutorial about advance use of Binary Search for solving questions. Since as mentioned in the TopCoders's tutorial, it can be use to reject a part of search space where the required solution wont have probability to exist. Thank you
I made a playlist for Binary search with the intention of discussing Binary Search in detail. You can find it here:
Binary Search: ua-cam.com/play/PLMCXHnjXnTnvYoBsAzrwigA-HSvfVXNNG.html
idk why this channel is not growing, this is real gold .,, love you Gaurav
The best Dijkstra's Algorithm explanation on youtube. Simply Outstanding. Keep it up
Can you please make a complete vid tutorial on Graph data structure please. I haven't been able to find a good one so far. Thanks in advance. Your explanation is simple n clear :)
Thanks Sreekanth! Will get to this soon :)
good idea my man
Hello, Gaurav this was really helpful, specifically, the way you addressed the critical points that a student has to take out of the algorithm is simply spectacular !!
You were so excited with the introduction +100
your introduction is welcoming.
This is exactly what was happening to me, I didn't get how the hell it was working, thank Gaurav!!:) This is an amazing explanation i would surely recommend this to all my batchmates @IIITB
this was THE BEST explanation for this algorithm- nowhere else ! woow
Thank you 😁
Hey man! I have an exam tomorrow and this video has saved me in this peak time of crisis. Amazing work buddy! good going.
Thanks 😊
Dude learn for the sake of applying in the industry not for the purpose of passing exam
So if we have all edge weights equal to a same value. We can directly use BFS algorithm for calculating shortest path. Am i correct??
Yup!
very well explained! thanks so much :)
You are a great teacher with a good intuitive understanding and articulate presentation of what you intend to teach.
Please try to make a 'part 2 / extension' of most videos wherein you actually Code the whole thing in Java. That's where I and many others fell in love with your channel (referring to your Java C.P. training playlist).
Thanks Akarsh, will try to incorporate that in future!
what's up with the skewed views:like:dislike ratio?
Thanks for all the awesome contents !!!
Thank you :-)
the initial part pertaining theory was really awesome but Code is where it all went south :(
Sad to hear that Ajeeth. Any pointers?
Feels funny how all software engineers travel south to get a life yet they cant resist south XD
@@gkcs I think you could've explained a couple of iterations with actual figures like you did with the explanation.
It's actually pronounced as Daaikstra !!!
Dyke-strah!
Angrezz ki auladd!!, uski Marji Jo mrji bole woh.
Every thing you taught was FAB!
But brother the worst time complexity for Dijkstra Algo is O(n^3).
9:40 All the unvisited nodes will have distance infinity. How are we comparing distances and choosing node with minimum distance?
The 0th index in distance array has been set to 0. So it will be the minimum
Happy teachers' day to the amazing teacher!
@shalini
Code starts at: 08:47
What does the variable L[u][v] address?
For adjacent vertices you have to check if they're not visited, I think you've missed this condition!
i really appreciate your work that you're doing. Thank you for this.
Really Helpful.!! 👌👌😎😎
Thanks Akash!
Hi your videos are actually very clear ,What i suggest is Make a seperate lecture on the most often used algos and DS in codechef LONG challenge,If there is any rarely used algos or Datastructures ,or any difficult mathematical induction,please do explain that as well,Ur videos are very Good
Thanks!
Thanks a ton!
In this example you explained the distance between d(0,4) is 24, but the shortest distance between 0->4 is 22 (0->6->7->4), similarly from (0 to 3) is 28 ( 0 -> 6 -> 7 -> 4 -> 3 )
Rakesh Patil I don't think so. At 7:50 you can see how the two paths lengths are computed
OK....I got it
who the fuck disliked this video
Why infinity.?why not zero initially
The spelling of Dijkstra's algorithm on the video thumbnail is worng 'r' is missing.
Your videos are great you are helping many students to become great programmers.
Thanks for pointing that out Kapil! And thanks for the feedback :-)
Does dijiktra could also be solved via prism's by providing given node as source
I don't know why the number of subscribers to your channel are less than other channels , even though the content is so much better. !! I have loved each one of your videos, specially High Level Design videos. There are no better videos on youtube for HLD. And thank you for replying to all queries in comments . I don't know if anyone else does that! I am going to share this channel with all my friends preparing for interviews :)
Thanks Neha 😁
Is this using matrix or list priority queue?
I guess, it is graph with greedy algorithm
bhai isme proof kahan tha?
We know the ds used in prims and dijkstras is min heap but how the min heap works with dijkstras and prims can u plzz explain
Hello I would just like to say this is a very good video and you have explained this very well, but do you know how you would code this in VB. I already have made up a network of verticies but i dont know how to get it into an array?? please help thank you!!
(I only want to have 6 nodes and 8 paths but i do not know how to code the algorithm)
Awesome :)
For what f variable taken
Crystal Clear :) Thanks bud ....The most confusing part is its pronunciation lol
It's pronounced as how it is written. Di-jik-stra! Lol
@@hawktomnia007 it's actually di-ks-tra
you are really awesome bro :)
Thanks Mahim!
implement it using any language like c, java , etc then i will believe it works. my point is it does not work
Sir pls help us by teaching Kruskals algorithm(Union-Find by Rank).
Abdul Bari's explanation is better.
it's a greedy algorithm and not a dynamic programming algorithm.
It is a dynamic programming algorithm :)
@@gkcs dijkstra is a greedy algorithm
@@gkcs It is actually both greedy and dynamic programming algo. It uses greedy approach to select a node and while exploring its neighbours it uses dynamic programming approach to update distances.
is it dijik or dijk?
nice
Hi Gaurav!
I have a doubt.
is the while condition correct?
since our source node is not there in remaining collection of nodes in graph.
would not it be N-1?
i.e visited.size() < N-1 ?
or else should not we add the line visited.insert(source) just below the set creation?
Hey!, Can you tell how should i go on solving problems. I get the concepts and have solved 50 problems on SPOJ but still struggle on most basic problems. It would be helpful if you make some tutorials on other graph algorithms and suggest some good problems to solve in the end of videos.
Hi Tanveer! You could try to regularly participate in contests and pick up on one problem that you couldn't solve. That teaches us new algorithms pretty fast.
Hey, thanks man.
Does dijiktra also forms minimum cost spanning tree ?
No, It finds out the minimum path from the source nodes and for finding minimum cost edges you need to tweak the weight update part a bit
Virgil Van Dijk...
Could you please explain the difference between O(Nsquared) and O(ElogN)?
Is the difference in complexity happening due to the size of the graph?
Or is it happening due to the minExctract() function which can be minimised using a min-heap to obtain lower complexity. ?
Waiting for your reply Gaurav 😇
its pronounced "dike-struh"
Not a good explantion i think.. You should make your viewer's to visualize the whole thing in their mind.. and you also getting sometimes confused.. Sorry bro., what i realized..
Lol dude. It was good. You can read more about it and fill in the gaps. I do agree the explanation was not up to Gauravs standard, but was good enough
Solve this questions using Djikistras algo to truly learn it how it works
leetcode.com/problems/network-delay-time/
when to use dijkstra and when to use dvr?
What is DVR?
Great!!
Thanks Rushikesh!
Gaurav Sen Can you make videos on other algorithms like flood fill,KMP advance sorting algorithm such as bucket or radix sort?
It would be great!
how come that 30 became 28 it should remain 30 only????
That 30 becomes 28 because 28
why does this algo work tho......
Very good question 😛
Isn't the pronunciation of "Dijkstra" something like Dykstra???!!!
Yeah, he misspelled and mispronounced the name. It's spelled Dijkstra and is pronounced something like Di-ek-straa.
Dude.. Are you on Codechef.??.
You can have a look at the link on the channel, or search for gkcs there :-)
Thanks:)
Damn !!
Who's here hours before the exam ?
well I guess you failed it then xD
@@Endrit719 negative piece of shit.
@@Endrit719 the joke here is that exactly in 3 hours I have the final paper for the same exam..😂
dijkstra*
Its Dijkstra's not Dijikstra!! Correctly pronounced as [Dai-stra-'s].
I know 🙈
nice