Graphs: Dijkstra's Algorithm

[@kingofwebguru]

Short and easy to understand. Great job. Hate books that spend pages over pages that make you want to burn it all.

[@thodap1]

Excellent explanation, I just passed an exam because of this video, god bless you!

[@ArwensarYunikoCreations]

you explained 1 semester in 10 minutes

[@dvorak2676]

what school and what year ?? wtf

[@ammadahmed8811]

30 minutes of my Data Structures and Algorithms lectures. I think you belongs to mid of 20th Century

[@Vrbik15]

fuck your school then

[@tianyuchen1802]

We just explained that for 30 minutes,elps...

[@ashishnegi3848]

is it so?? advanced? we are studying this in our 3rd sem and it comes of only 8-10 marks...it's an average level of problem.

[@GtaRockt]

thank you! My Uni professor just explained this in such a complicated way.. and you do it within 10 minutes in such an easy way! you are the best, I love you.

[@Athanazeus]

that's how you squeeze an hour of course into 10 mins

[@me-zb7qm]

This video is more than 10 years old, yet still so useful. Going into exams with more confidence after watching your explanation, thank you!

[@Vineyverma]

Very well explained. Explaining complex things so easy is really an art. You are an artist. Thank you and Good wishes to you.

[@joetron5114]

This is the best explanation for Dijkstra's that I have seen on the net. I was having a hard time with this algorithm until I saw it explained like this. It helped me finish my project. Perfect!

[@euclid9492]

This one was very helpful. The other video I watched gave me the impression we chose the new vertex from the list of unvisited adjacent vertices because the graphs were too simple. This one was complex enough (having h have only one path leading in) that it made it clear we are choosing the next vertex to check just from the list of unvisited vertices. Thank you.

[@mostafaeldeep7539]

Thanks alot man I passed my exam last year because of this video , thanks from egypt .

[@max29297]

Now to find other paths, for example, as you said, D to H or H to G, you use the same method that the instructor used in this video. Notice that the instructor started with A - this was his starting vertex. To find a path from a vertex other than A, simply use the same method starting with that vertex instead (for your problems, D or H respectively) Hope all of this helped! :)

[@4ourTimber]

Explained much better than my lecturer! Thanks!

[@Masenken]

wow, now if math teachers could find ways to be this straightforward and concise in their teaching, we'd all be astrophysicists by now. Nice explanation

[@lanesetrimmingham3331]

I don't leave comments, but I had to say a job well done with this explanation. Just perfect!!

[@volrath__]

These have been really good for revising for my Data Structures and Algorithms exam today! thank you :)

[@lanoche]

helped a lot, managed to learn more in 10 minutes with your explanation, than with my prof's lecture that took 3 hours

[@TheSyncan]

B:20, C:40, D:50, E:N/A, F:30, G:70, H:60. For clarity, ignore the "small letters" under the numeric line values; they represet the "via node". Each line value from left to right aligns with each Goal Node's "main column", starting with B (focus on the letters written in blue at the top). That stated, to get the shortest path from A to Goal n: read *only* the numerical values on the final line (#7). (first value is for B .. last value is for H).

[@anasfcb]

Thanks a Lot !! I have Exam tomorrow too !! This algorithm has been a headache to me for a long time untill I saw and understood your very good leçon a few seconds ago ! Thanks again Sir !

[@ddd222444]

Amazing man , really thank you, I have a final exam tomorrow and your video and easy explaining was too helpful for me , Keep on

[@bharatraturi]

fantastic one. i had been trying to understand this for a long time but this video really took very few of my time to make me understand

[@excel20]

You take a look at the values in row 7: G can be reached the fastest via D (as D is the last vertex mentioned in column G) D is reached via C, C via F, F via B, and B via A. So to reach G by the shortest path, you go A->B->F->C->D->G

[@RoyalSwish]

This algorithm is so annoying, thank you for making it more clear than the textbook.

[@travolta91]

I'' be sitting for Data Structure final exam paper in 3 days time.. You just saved my life!!~ :) :)

[@NoorAhmedAboiye]

Excellent!!! you made it really easy to grasp in 10 minutes than a full class lecture. Thank you very much, keep up the good work.

[@ThisaraPinto]

You just saved me for my final exam! This is the only problem I had trouble with. Thank you!

[@UnrealLotus]

I have an exam tomorrow and you have just saved my life! Thanks!

[@TheRuinedUniverse]

I like it! I'm going to pay him a visit in the Bath House, in Novigrad, I believe congratulations are in order!

[@vojtechjanku2534]

Yes! Finally someone made a Witcher reference. I was browsing xkcd and suddenly "Dijkstra's algorithm" came out of nowhere. I was like "What sorcery is this??"

[@TheRuinedUniverse]

Vojtěch Janků Ahaha 😂😂

[@kamoroso94]

I'm glad I found this video. I'm working on a project for class that requires this algorithm.

[@janashafi6674]

Soo simple and easy way of exaplaining. Hats OFFF

[@c.harris7823]

This is an outstanding video. The only example or scenario that seems to be missing is how to manage/make a decision when you have two (2) edges from the same node (so two different path options from the same node) that cost the same...e.g. going from F to C or from F to D and they both cost 40.

[@kristijanceple6026]

Note I'm just a student practising this, so I'm not sure if it's correct but seems to have worked and made sense, at least for me so far. But still take it with a massive grain of salt, and if somebody could correct me that'd be great choose either one, just make sure it's the shortest one or among the shortest routes as calculating using shortest routes is the whole point of the algorithm. Also if to a certain node you have got 2 paths of the same length, just write something like 60, (A, D) down into the table. For example, if both A and D lead to E at a cost of 60 each, write 60, (A, D) under E. Then you can pick either one, the point is just to cover all the nodes.

[@gregorygofman1155]

Very nice, I think you saved my mark for this semester. Cheers from Russia

[@nafnaf6002]

OMG that was amazing i was desperate to understand this thing cause there are only 4 hours till my final and then i found this tutorial when i was revising thnq so much you saved me

[@imismael]

You usually use a secondary criterion for selection. In our class we select according to alphabetical order. For example, if A -> C = 20 & A -> G = 20, we select C as it comes first in the alphabetical order.

[@pratapbhanusolanki6613]

An awesome explanation with a great example. You have covered all of the possible trickiest cases. Thanks a lot :)

[@ragnarokl3923]

Thank you very very much. You explained it well and I understood it well. My teacher didn't haven't taught us this (as far as I remember), but gave us an assignment which we have to use this method to solve (it said so in the problem, as in we have to specifically use this method). So I'm really really thankfull for this video. Once again, thank you.

[@noobdevtutorials50]

Understand it without any difficulty.Thanks man.

[@thatAdamskid]

Just wanted to thank you profusely. And also to say this is my first actual youtube comment. Hello world!

[@preritdatta]

God Bless u made it as simple as a childs game!!! Thanks to you,I can now score well.Thanks a lot man!!!!! keep posting!

[@AndreiPetre]

to get a best path, take for e.g. the best path from A to D (obtained with Dijkstra's alg), you follow the reverse path given by the parents from which they were explored. So starting from D, you see that it was visited from parent C and has a cost of 50. Now going to C, you see that its parent is F. And F was visited through B (its parent). And finally, B's parent is A. So the path would be A-B-F-C-D. The idea is that you have to reconstruct your path from _goal_ node to the _starting_ node.

[@ocb2112]

wow i have been searchin through my skripts and through wiki to learn that stuff. but that was the best explanation by far! good job and thank you!

[@Zerpentile93]

Wtf. Didn't know it could be explained so easily. Thanks!

[@JoeBuza]

Can you believe this is a 5 year old video? Good work mate

[@sumeyayenzaismael5727]

kkkkkk

[@leggermentesara]

Now it's 10 year old 😱

[@AlexGomez-rv2ny]

Can you believe that your comment is 4 years old?

[@vim1729]

Hiii

[@iam_topg]

its 11 years now lool

[@JohnSmith-hn6kv]

This is the 3rd algorithm you've taught me!

[@MrTeetam]

The TSP is the hardest problem to solve, as it is an equivalent problem to all of the other hardest problems (the rest of those that are NP-complete)--what you are describing is a probabilistic approach which will estimate (but can't guarantee) an optimal path, which one could argue isn't a solution as the problem is to find the optimal path which you may or may not have done with this.

[@towhidskynet]

I love your explanation about algorithm. what is your youtube channel ?. your explanation on BFS and DFS destroyed my 15 year old fear about Graph problems. you explain things 1000 better than a Professor of MIT. Thank you !!!

[@ComputerScienceExplained]

+Mubeen Ali pretty sure he was watching open courseware and was confused by a university presentation that explains theory as well...

[@ervinzhou8251]

I mean I thought the MIT lecture guy explained it pretty well..

[@cellardoor8943]

nice man ! i was trying to understand what " vertex relaxation " was and i got it from your video

[@graysonwebb2018]

Really well explained! And easy to remember. Text books should teach this way of doing it, much more pedagogical.

[@nawkwan]

Thanks for this clear illustration and explanation. Good Job.

[@nikkei5410]

Best Explained I've ever seen.

[@OnlineSGNTheFishBoss]

this video helped me in my final exam.... THANKS A LOT !!!!!!!

[@wendygal6910]

You rule! you are the only exapmple like this put there! and Ive been looking for like 2 hours. Thank you :)

[@PotionDweller]

Thank you so much, this was fantastic for clarification. Watched two of your videos so far and they've been very well done.

[@darkcarney1]

Awesome, Exam later today and was totally blanking on Dijkstra algorithm Thanks heaps

[@Dimme]

What I've concluded is that I need to keep applying Dijkstra's algorithm until my destination node is marked as permanent. Then I can stop and I don't need to visit the rest of the nodes. This makes the algorithm a little more efficient.

[@Ben1220]

So well explained that my Grandma understood it!

[@MrTeetam]

This is a completely different problem to what you describe (TSP). Dijkstra's algorithm finds a 'single source shortest path', and so it computes the shortest path from A to any other vertex. It doesn't require that all (or any) of the other points be included in the solution's path.

[@AleksandarGeyne]

Really helped, man !! I watched this video an hour before my exam, went there and nailed it !!! :D

[@leggermentesara]

Thanks! 🔝 10 years later 🌱

[@29leej]

finally the video for directed weighted Dijkstra graph.

[@annevyner]

Thank you soo much i had finals 3 hrs later, i just needed to und this part and im done, Thanks to you u saved hours of mine. Keep it up!

[@AlexWard94]

Incredibly helpful video - completely ironed out my confusion with this topic! Thank you! :D

[@Tgasparian]

This is much better than my text book explanation

[@tqbfjotlddltojfbqt]

Very good tutorial, it be even better if you talk about how using a min priority queue is improvement over original algorithm Dijkstra submitted in his paper

[@smartalex32]

Whichever one you get to first is the one you use. They both are valid paths though, so you can technically use either one.

[@oguzhangoller697]

Best explanation so far, Great Work !!

[@AbyssenTheHoly]

Dude. Thank you so much. This helps me a LOT, I have a final tomorrow!

[@U0ykcuf]

Thank you so much. My textbook is super vague on this, and now I finally understand.

[@mbawaters]

Going from Vertex B to F without processing other neighbors of A is a digression from BFS approach. More often Dijkstra is considered BFS with greedy approach.

[@Nictron80]

Thanks a lot, this will help me with my test next Tuesday. :)

[@Cdoddsy]

College final in 3 hours and 1/3 of it is going to be on this. I have not shown up to class once and now I am cramming. Pray for me.

[@twistedflamingo1]

No, the shortest path isn't the order of the letters in the first column. The path would be A to B to F to C to (both D and H) and then from D to G.

[@amizan8653]

Thanks a lot for posting this, it makes perfect sense now

[@max29297]

To answer your first question: Yes! Vertex A is your starting node. The highlighted distances at the end of the video are the shortest distances from A to every other vertex.

[@The1311714]

Thanks so much, It's helping me for my test tomorrow.

[@yashithayasanga9985]

me too

[@semifuntastik]

thank you very much amigo, your time and effort is greaty appreciated

[@colonelbastian6036]

Best dijktra demo. evar

[@h34rtk0rps]

Heh, you're much better than my professors at explaining stuff. Would have thrown a like your way...

[@Kemenesfalvi]

This is not about going somewhere and staying there, but if we want to go to H he found the lowest cost path there, but if we want to got to G we have a lowest cost path there too which doesn't include H but goes on from C .The solution shows all the lowest cost paths for any point

[@syedhamzah3324]

A very good explanation, very helpful for my exam!

[@imorio]

@elgonost You could choose a random path, or the path given by the algoritm checking for the lowest number. I suspect you could enhance the algoritm to track both paths in that case. Now it only finds the shortest path to a point, if you rewrite the algoritm to track both and continue further steps seperatly, you'd get an algoritm that gives all shortest paths to all points.

[@max29297]

To find the order, work backwards. Find the highlighted distance for your destination vertex and look at the letter beneath the distance. Write it down. Now look at the letter beneath the highlighted distance for the vertex you just copied and write IT down. Continue this pattern 'til you get to the start and reverse the list.

[@SPyoutube42069]

a quite nice visual explanation, good stuff

[@viharsarok]

@manojsam79 You only need the last row. Begin at the vertex you're interested in, look up its parent (the node that's written under the optimal cost), than look up the parent's parent etc. Proceed until you reach the starting node. Reverse the list of nodes to get the shortest path. E. g. the shortest path to H is H, C, F, B, A reversed, that is A, B, F, C, H

[@MrSyKoM]

Thanks, this helped me. I have to specify that this is no the Djikstra original algorithm: this is implemented choosing the min vertex (with a min heap), the original algorithm choses the first node of a queue. Anyway, it does not change the core buisness :) Thanks!

[@silversvartnad]

Thi vid makes it very easy to understand the algorithm. Thanks a lot =)

[@rene13cross]

This must be one of the only 16:10 vids on KZbin :D Thanks for a great explanation btw

[@piurek10]

good explanation thanks from Poland.

[@arngorf]

This is absolutely brilliant. Just what I needed! Thanks!

[@darrylbil]

AWESOME !!!!! U SIR JUST SAVED A LIFE

[@ahmedrezwan3856]

No doubt it is the best explanation ever

[@4.0.4]

Only gor the sake of a clarification; the "traveling salesman" problem you describe is not the hardest problem to solve. It's just somewhat hard if you want to brute force all paths (which is silly), but even that is not too hard by moderns standards (You can brute-force it in a GPU with CUDA now a days!) You can "solve" it cheaply by using genetic algorithms. Look it up :) Also, it's been thaught for too much time in universities by teachers who don't like to keep up-to-date.

[@ahmetturan4783]

Thank you. You explained pretty easy to understand.

[@DavidRutten]

Well done, excellent description. But why no rating?

[@dheerenr]

Thank you soo much, by far the best explanation ive found :-)

[@muhammadsaad6101]

Watching this after like 9 years of it. Wow.

[@saurabh1qaz2wsx3edc]

thnk u so mch... have xams in 8 hours :P . thnx 2 u... will at least score 5 marks for Dijkstra algo :D

[@lizard2728]

Thank you -- awesome explanation! I'm needing to implement the algorithm, and this helps tremendously!

[@CGagnon5]

I really like this notation. Thank you!

[@liamMaru]

It's just mathematically convenient, because we want to take the minimum weighted distance, and there exists no number larger than infinity, therefore we can assume ANY path is better than none at all (infinite distance). Does that make sense? The use of infinity doesn't change the algorithm, but it can greatly simplify the readability of its implementation (IE, if your language is IEEE 754 standard and recognizes infinity)

[@TheSyncan]

The shortest path, of all in the return set, is A->B=20. But that's not the intent nor the answer for this problem. The algorithm returns a *set* of shortest paths (B-H), given a topology of nodes with multiple connections (or edges). Not just a single, shortest path.