How Dijkstra's Algorithm Works
Вставка
- Опубліковано 19 тра 2024
- Dijkstra's Algorithm allows us to find the shortest path between two vertices in a graph. Here, we explore the intuition behind the algorithm - what information we need to keep track of, in what order we need to explore vertices, and what the limitations of the algorithm are.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Came from Computerphile's video after not understanding, and this is just so much better! You made advanced concepts so easy to understand for beginners like me, thank you.
Here's the implementation in Python
ua-cam.com/video/VnTlW572Sc4/v-deo.html
Same! Came from Computerphile, felt dumb, watched this, and understood.
Same, concepts should be intuitive for humans.
@@TainuiaKid1973 I also came here after seeing Computerphile video😂..
This video is criminally underrated
This video is ridiculously underrated ((
istg
Can't agree more
I noticed that people put everything between is and underrated
Truuee
Criminally underrated, Brian Yu also teaches in Cs50 topics like AI and Web dev
THANK YOU for the part at 6:28 ! Nobody else seems to explain how to actually find the path, and not just it's length.
I've been agonizing over trying to understand this algorithm for a class for hours- and now I'm about halfway through this video, and I'm already feeling enlightened. It's FINALLY clicking. You're a lifesaver, mate!
I cant stress how amazing these animations are! You are a livesaver for "self-learners" like us :)
Absolutely!
fuck, dude, yeah. I don't learn anything from my college lectures- I need stuff I can pause and rewind, and my monkey brain does great with visual assistance. needing to basically self-teach myself all my CompSci, I don't wanna think about where I'd be without videos like this
Learn your real name first!
Calling yourself a self learner is meaningless. Everyone is a self learner.
@@MikhailFederov There is a more respectable term for self-taught:
Autodidact.
I love learning based on examples and this is by far the best example of Dijkstra's algorithm I've seen so far. It covers a lot of aspects that might not be obvious at first. I haven't even learned Dijkstra yet, but it feels trivial to implement after knowing how simple graph algorithms like DFS or BFS work.
The animation is just outstanding!
A video on "how" you make these videos or just what inspired you to get started on this creative journey would be awesome.
Keep up the amazing work. I have subscribed and also pressed the bell icon. :)
By far the best video on this subject I have ever seen, FANTASTIC job with those animations they are really good!
So far the best and easiest explainations i have ever seen on YT yet for dijkstra;s Algo. Great work !!! Thank you :)
Not only the video is underrated but the whole youtube channel is underrated. best of luck you spanning tree. This is the future of education. I feels so good when i look up to such unique educational channels.
One thing I realized, visualization is more helpful to grasp a context than just reading about it.
Absoloute life saver. Got taught this by a teacher who literally doesn't know computer science so videos like this are vital.
Please continue to do more of this video! Thank you so much for your content!!
It's amazing that I recognized this voice immediately and realized this random video I picked is actually from Brain! Thank you for all the hard work you've done!
Such a great way to explain the complex topic. Thanks a lot. 😊
I've been watching a few of your videos over the last day or so, and they're all just so good. You really have a knack for explaining complicated concepts with a clear, easy-to-grasp visual style. I think I'd describe your channel as "3blue1brown for computer science" :) I hope that comes off as complementary as it's intended. Kudos, and keep up the great work, I'm looking forward to more!
A very helpful video. Just looking at code and some rambling explanation in a book made the algorithm as clear as mud in a beer bottle to me... but this video has made it so abundantly clear... and seeing how code is derived from it is more than helpful. Thanks so much for posting.
This is the first video I watched on your channel and on dijkstra's algorithm and damnn it was sooo good! Loved it!
What a great explainer video! Please make more of algorithms. Thanks a lot for making this video.
For each vertex v:
Dist[v] = infinite
Prev[v] = none
Dist source = 0
Set all vertices to unexplored
While destination not explored:
V = least valued unexplored vortex
Set v to explored
For each edge (v, w):
If dist[v] + len(v, w) < dist[w]:
Dist[w] = dist[v] + len[v, w]
Prev[w] = v
Thank you to SpanningTree for the insight and thank you for the memo !
What's the significance of Prev[w] when the latest update of Dist[w] is more important?
@@abam9787 6:24
@Skidoodles the last two lines should be indented more, to indicate they are both part of the "if true" branch of the conditional. Also, why not indent for the while loop?
Thanks man
This channel is a germ!! So glad I found you!
very interesting!
i love how you voice over your code. you make it super understandable!
This is the best explanation on Dijkstra's algorithm I've ever come across!! 🙌🙌
This is so much better than some other ones I already saw....and that was a nice tip at the end, referring to the negative value.
Very great explanation, I just followed along Dikstra's algorithm in pseudo code and implemented pathfinding in Unity using it. This visual tool really helps explain the algorithm at hand! Great work.
Incroyable ! Mes profs n'ont pas réussi à ma faire comprendre cet algo en 1h et là je tombe sur cette vidéo ! Merci tu viens de sauver mon année !
you're videos are extremely helpful. thank you for making these! Also love the robot
The ambience,sound the illustration and putting the main logic behind this algorithm : Clarity and transparency are optimum.Please do make videos like this for every important algo,a request.Refreshing..
No doubt like many other people, I reinvented a variant of this particular wheel (in my case back in the mid 90s while writing "AI" code for NPCs at a games company).
A guy on our team who actually liked writing in x86 assembly language had written a brute-force A-B routefinding function that was slow enough to take up meaningful time.
After some playing around in C, I ended up zeroing in on the offspring of Dijkstra which fully explores the graph and finds the shortest routes to everywhere, and it was several orders of magnitude faster than the assembly guy's code.
i have my Alevel Comp Sci paper 12 hours from now. I love you man. Youre a real life saver
Excellent illustration of the Dijkstra's algorithm. Superb!
Excellent walkthrough. 4th video down and I finally get it. Thanks
Kudos to the animation and explation.
The first time I figured out this algorithm, it was by reading code. That worked, but took way longer than watching this video. This video is very nice. It is clear and touched the most important points. You've made an intuitive understanding of Dijkstra's algorithm easily accessible to anyone. The only thing I would add to this video is at least a brief mention that you would put the data in a heap. This could be a nice segue into a separate video about heaps.
I saw this in a class in 1994 or 5. This has always been my favorite algorithm I've ever learned. Nice video
I love this explanation is so simple to understand. Thank you!
Excellent video. Clear and concise description of Dijkstra's algorithm.
Thank you! You've made it so easy to comprehend
You need to post more, those videos are freaking good
I am sharing this link with my students in the Data Structures course -- Keep it up!
I don't know why YT is recommending this to me 2 years after its upload, but I gladly clicked on the video! This is pretty much the only thing I remember from when I was studying Geoinformatics before I quit lol so it's a nice throwback for me. Very well explained too! 8:30 for something our professor needed like 2 weeks for
This is almost similar to the CPM (Critical Path Method) that we study in Project Planning and Management. So beautifully explained
Just wanted to mention that. You're absolutely right 🙂
This is the best explanation,one can ask for. . Waiting for more such algo explanations
Awesome explanation, short and to the point.
Fantastic video!! Am watching all your videos back to back
By far the best explanation on the internet. Thank you
I have a shortest path problem that I am currently working on, and even though I am familiar with the Dijkstra algorithm this somehow just made me instantly realise of my mistake in code. Gracias
thanks! easy to follow. explained in simple terms.
Really cool stuff. I am also happy about the snippet code algorithm at the end
I don't think I've ever watched anything ever explained in a clearer way than this.
Just gotta a say, thanks a lot.... U have made it so easy to understand... The animation is very helpful... Keep going
Great, clean and simple!
Congrats!
I loved the video and your explanation.
I read something out there and I want to share it
3:47 - 4:42 "It's important to note that this approach may have limitations and doesn't always ensure the most accurate result. In certain situations, it could lead to inaccurate estimates if the initial estimation doesn't precisely reflect the reality of the path. In the original Dijkstra's algorithm, continually updating estimations is crucial to ensure the accuracy of the shortest path."
Exactly what we need more of! Amazing explanation
not even kidding this is the best explanation/ visualisation one can ever get Thank you sir!!
Your channel should grow! Amazing work!
Amazing job! I have a logistics course in uni and I didn't understand the class. Lucky me found this video. Thank you!!!
My professors love bringing up the traveling salesman problem and then not elaborating, so this was fun. Thanks!
Most grandiose of respect,
the other day I saw a video that jump straight to explaining the 'cost'. Me being a non technic person can't understand why a to b took so long, while you can just hypothenuse your way to b.
But now it makes sense!
You guys have produced super videos..thanks much!❤
Damn, I recognised Brians' voice from CS50AI. Respect for your joy of teaching man!!
Very well explained! The only feedback I can provide is that I personally found the background music annoying. The wind instrument (flute?) seemed a bit obnoxious and interrupted my focus on the concepts being presented pretty often.
Kind of hard to know that sort of thing ahead of time, but that's just my personal experience of the video. :)
The music makes me want to kms
Agreed, itd be better without it
Great video and audio visual representation of the complex algorithm. Made it look like so easy for anybody to learn. Can we have a similar video maybe for A* algorithm, that would be pretty awesome. Also any algorithm google might be using for their routing solution. Thank you.
Great video with clear explanation! It would fit those entry level guys.
This is amazing. Please keep the good work.
Really great animation for explaining the concept, loved it
The amazing quality of your videos is super underrated
I am taking CS50 Edx class, I recognized this voice. It must be you Brain. Wonderful job explaining this concept, just like you did in CS50!
This is incredibly well made!
Besides how great of a job this video explains this concept, The absolute best part is the little blue robot blinking and looking around.
Very helpful video. Im a Network Engineer and this is how OSPF works (because it uses Djikstras Alg.). Instead of towns, its nodes (routers) on a network.
By far THE best graphical explanation of Dijkstra's algorithm and it covers improving it to get the actual path 👍
Great video, very intuitive and help me a lot!
Wow just so amazing to get Dijkstra algo visually understandable. Thanks a lot for making such a great animation, it was really very easy to understand visually. By the way which tool did you use to create this interactive animation. Thanks
Great video! By which kind of tool did you make such great videos? Thanks for sharing!
Please add more algorithms videos like this. Thanks!!
From Google Maps to Project Management (CPM) the applications of this algo are literally limitless
After watching a few videos on this, for some reason the robot and town animation made the concept finally click. Thanks!
This video had actually insane timing. Just went over this in class.
you are just doing a great job right there, Thank you
my god this is amazing!!!!! How expert you must be at your art to be able to simplify to this extent
beautifuly explained! Dont stop making these videos. You are the savior of cs students
This video is amazing, thank you very much for this help!
this is just mindblowing, keep creating content like this, you will reach to million subscriber within no time
I see everyday at my work that when one is able to easily understand a concept or idea, either the subject is assumed to be easy or the person learning it assumed that all the merit is hers/his.
… But if it takes a big effort to understand an explanation, then for sure it is always the fault of the one providing it.
The fact that you can perfectly understand something does not mean you can easily explain it to others: *Explaining things is not trivial* and if you watch a video and get the idea straight away, please, do not automatically assume you are extremely clever but consider the effort made by the person providing the explanation.
Thanks for this excellent video.
Beautiful explanation. Thank u so much.
This was really very insightful. I wish more teachers would adopt this method of teaching because it is so much easier to understand than the traditional textbook method!
Making a high quality UA-cam videos like this takes a lot more time than drawing nodes and edges on a whiteboard.
While giving high quality lectures on white board is skill. Honestly, our education system is fine, just the skill issue of conveying an idea. Fucking hell my "international university" profs can't even speak English.
Best video explanation out of them all, thanks !
perfectly explained, intuitive well ordered and perfect example.
great work
I used the Dantzig method to do this. Now I understand a new method, thanks
How this video have less than 30k views!! It deserves ar least 1M, I really understood it so well thank you so much
Best video about dijkstra algorithm I have ever seen
Very useful! Thank you very much for doing this video :D
Brilliant explanation. Thank you!
Hey this is incredible thank you. Is there any chance at all of you doing a video on the Simplex Algorithm for linear programming problems at some point? That would be great
i never subscribed a channel just watching one video before..You are so good
This channel is so good.
Very clear explanation, thank you!
Also...a great voice too. Very clear.
This is Amazing!!!
Thank you so much for the video!!!