How Dijkstra's Algorithm Works

Подписаться 189 тыс.

Просмотров 1,3 млн

50% 1

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.

Опубликовано:

20 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 730

@hongweichen3581 3 года назад

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.

@TainuiaKid1973 2 года назад

Here's the implementation in Python ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-VnTlW572Sc4.html

@Itachi.Uchiha.Offical 2 года назад

Same! Came from Computerphile, felt dumb, watched this, and understood.

@turuus5215 Год назад

Same, concepts should be intuitive for humans.

@dineshkumare1750 Год назад

@@TainuiaKid1973 I also came here after seeing Computerphile video😂..

@nayankumarbarwa4317 Год назад

This video is criminally underrated

@beketmyrzanov1979 3 года назад

This video is ridiculously underrated ((

@vn5051 3 года назад

istg

@travelrealindia1 3 года назад

Can't agree more

@thishandleistaken. 2 года назад

I noticed that people put everything between is and underrated

@myleshayhurst5187 Год назад

Truuee

@nayankumarbarwa4317 Год назад

Criminally underrated, Brian Yu also teaches in Cs50 topics like AI and Web dev

@aries3690 2 года назад

I cant stress how amazing these animations are! You are a livesaver for "self-learners" like us :)

@acedev003 2 года назад

Absolutely!

@Yell-Heah 2 года назад

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

@MichaelKingsfordGray Год назад

Learn your real name first!

@MikhailFederov Год назад

Calling yourself a self learner is meaningless. Everyone is a self learner.

@MichaelKingsfordGray Год назад

@@MikhailFederov There is a more respectable term for self-taught: Autodidact.

@Mobin92 Год назад

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.

@supersakib62 Год назад

One thing I realized, visualization is more helpful to grasp a context than just reading about it.

@Yell-Heah 2 года назад

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!

@dominiorrr6510 Год назад

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.

@skidoodles 3 года назад

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

@adharlak510 3 года назад

Thank you to SpanningTree for the insight and thank you for the memo !

@abam9787 Год назад

What's the significance of Prev[w] when the latest update of Dist[w] is more important?

@AlumniQuad Год назад

@@abam9787 6:24

@irrelevant_noob Год назад

@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?

@ayeyebrazof6559 Год назад

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 vertex 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

@whatsup_internet 6 месяцев назад

So far the best and easiest explainations i have ever seen on YT yet for dijkstra;s Algo. Great work !!! Thank you :)

@penguinjuice7543 Год назад

Absoloute life saver. Got taught this by a teacher who literally doesn't know computer science so videos like this are vital.

@ujjwalgupta4160 3 года назад

Kudos to the animation and explation.

@prashanthvaidya 3 года назад

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. :)

@keitumetsemolefe3515 Год назад

This is the best explanation on Dijkstra's algorithm I've ever come across!! 🙌🙌

@ozboomer_au Год назад

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.

@pend_deletepatrickguarente4916 9 месяцев назад

By far the best video on this subject I have ever seen, FANTASTIC job with those animations they are really good!

@soyandoat4106 2 года назад

Please continue to do more of this video! Thank you so much for your content!!

@demonking2526 Год назад

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.

@chrisogonas Год назад

Excellent illustration of the Dijkstra's algorithm. Superb!

@johnle7705 3 года назад

This channel is a germ!! So glad I found you!

@BrianOSheaPlus Год назад

Excellent video. Clear and concise description of Dijkstra's algorithm.

@adrienw4704 Год назад

very interesting! i love how you voice over your code. you make it super understandable!

@ajaysrinivas2814 Год назад

What a great explainer video! Please make more of algorithms. Thanks a lot for making this video.

@qazizayad Год назад

i have my Alevel Comp Sci paper 12 hours from now. I love you man. Youre a real life saver

@KingstonFortune 2 года назад

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.

@magik0630 3 года назад

Excellent walkthrough. 4th video down and I finally get it. Thanks

@alliepiper4772 3 месяца назад

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!

@artycrafty8691 Год назад

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.

@taumah7302 Год назад

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 !

@davngo 3 года назад

Awesome explanation, short and to the point.

@rockstarpesu 10 месяцев назад

Such a great way to explain the complex topic. Thanks a lot. 😊

@jaylensung7332 10 месяцев назад

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!

@Mercury2wo Год назад

Fantastic video!! Am watching all your videos back to back

@DaveAlexKD 2 года назад

I love this explanation is so simple to understand. Thank you!

@smikkelbeer7890 Год назад

By far the best explanation on the internet. Thank you

@a.nataliia 16 дней назад

After CS50 that's one of my favourite voice on RU-vid ☺ Thank you Brian for your great work!

@dailyamazingshortvideos Год назад

This is the best explanation,one can ask for. . Waiting for more such algo explanations

@egalomon Год назад

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

@aakashdp 3 года назад

thanks! easy to follow. explained in simple terms.

@gargolario 2 года назад

Great, clean and simple! Congrats!

@kacperwodiczko 2 года назад

Thank you! You've made it so easy to comprehend

@saipan1970 Год назад

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..

@SaidElnaffar Год назад

I am sharing this link with my students in the Data Structures course -- Keep it up!

@soniahandle Год назад

Exactly what we need more of! Amazing explanation

@OneTrueBadShoe Год назад

I saw this in a class in 1994 or 5. This has always been my favorite algorithm I've ever learned. Nice video

@megamaser 7 месяцев назад

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.

@nawalkhawar7602 Месяц назад

you're videos are extremely helpful. thank you for making these! Also love the robot

@anilsuyal 27 дней назад

What an amazing explanation, that too with a visualisation. Thank you so much. Please keep posting such Visualisations of algorithms.

@ghanshyamtripathi221 5 месяцев назад

not even kidding this is the best explanation/ visualisation one can ever get Thank you sir!!

@manishmakode6332 11 месяцев назад

Really great animation for explaining the concept, loved it

@Agamista379 Год назад

This is amazing. Please keep the good work.

@Adarsh_Tiwari Год назад

This is almost similar to the CPM (Critical Path Method) that we study in Project Planning and Management. So beautifully explained

@TheMofRider2 Год назад

Just wanted to mention that. You're absolutely right 🙂

@shandou5276 3 года назад

This is incredibly well made!

@gowinidea Год назад

You guys have produced super videos..thanks much!❤

@s1mplelance964 2 года назад

Great video with clear explanation! It would fit those entry level guys.

@rocket007 Год назад

Really cool stuff. I am also happy about the snippet code algorithm at the end

@davewilson4493 Год назад

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.

@saragul2806 Год назад

Amazing job! I have a logistics course in uni and I didn't understand the class. Lucky me found this video. Thank you!!!

@rodrigo-tj1gf 7 месяцев назад

You need to post more, those videos are freaking good

@namankeshari7332 10 месяцев назад

This is the first video I watched on your channel and on dijkstra's algorithm and damnn it was sooo good! Loved it!

@matteobecatti3157 2 года назад

Very clear explanation, thank you!

@DC-zb7uf 2 года назад

Best video explanation out of them all, thanks !

@elijahdecalmer613 Год назад

Very great visualisation, thank you

@MartinStaykov Год назад

I don't think I've ever watched anything ever explained in a clearer way than this.

@SimonTheDankOne Год назад

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

@camerongray7767 Год назад

Amazing video. So well explained. Brillinat

@sayantankundu973 2 года назад

Just gotta a say, thanks a lot.... U have made it so easy to understand... The animation is very helpful... Keep going

@naughtiusmaximus Год назад

To understand Djikstra, you need to understand Roche and Ves's Theorems. And then Geralt's theorems.

@quadroninja2708 Год назад

I can't find anything about Ves's and Geralt's theorems. Could you please share some links to these?

@quadroninja2708 Год назад

oh i see, it's a joke :-)

@naughtiusmaximus Год назад

Its a Witcher joke :D

@repkins 9 часов назад

Every time I encounter Dijkstra name, I think about Novigrad.

@javel476 2 года назад

Best video about dijkstra algorithm I have ever seen

@SatyarthShankar 2 года назад

Your channel should grow! Amazing work!

@juanmauriciomugni5783 3 года назад

Thank you!! Greetings from Argentina, excellent video!

@amrutaj28 Год назад

Beautiful explanation. Thank u so much.

@HabunoGD1821 7 месяцев назад

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."

@abdullahmustafa3746 3 года назад

you are just doing a great job right there, Thank you

@DontAddMe Год назад

beautifuly explained! Dont stop making these videos. You are the savior of cs students

@minhlaburninghihi5627 3 года назад

Coolest video on Dijkstra's ever. So easy to understand, thank you so much.

@gutzimmumdo4910 Год назад

perfectly explained, intuitive well ordered and perfect example. great work

@stith_pragya 6 месяцев назад

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@minhucbui9566 Год назад

Brilliant explanation. Thank you!

@df_iulia_estera 2 года назад

Very useful! Thank you very much for doing this video :D

@JamesCheng999 2 месяца назад

Great video, very intuitive and help me a lot!

@sandhyav410 2 года назад

Wonderful explaination and beautiful animation..thank you🤗

@ccsmooth55 Год назад

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.

@rpgprime Год назад

By far THE best graphical explanation of Dijkstra's algorithm and it covers improving it to get the actual path 👍

@tyronefrielinghaus3467 Год назад

Also...a great voice too. Very clear.

@Gooloso98 3 года назад

nice video, especially the negative values and heap

@micokun8433 2 года назад

very clear and informative

@CrescentDolluwu Год назад

Besides how great of a job this video explains this concept, The absolute best part is the little blue robot blinking and looking around.

@josiasbudaydeveloper5864 Год назад

This video is amazing, thank you very much for this help!

@ikuubi 7 месяцев назад

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!