Dijkstra's Algorithm - Computerphile

[@TheRoboticLlama]

To understand recursion, one must first understand recursion.

[@wesofx8148]

Stack overflow.

[@wesofx8148]

Navaron No, his joke gave me a stack overflow.

[@vivekpal1004]

WesOfX You need a base case.

[@DigGil3]

Should have added some recursion limiting flag...

[@Oshyrath]

That's deep

[@MrNacknime]

I think this type of video is exactly the level of complexity your channel should be at. Stuff around the first undergraduate year of a typical Computer Science student, well explained is understandable for the average viewer but also interesting enough for advanced viewers.

[@billy653]

We did dijkstra's algorithm in our second year of uni, but it still is appropriate for year 1.

[@adrianlowenberg]

billy653 I did it in high school, as well as A*

[@lucas34540]

Welcome to the Mike Pound fan club. Far and away the best presenter on this channel. There needs to be a Mike Pound playlist if there isn't one already.

[@anishsarkar120]

ya most advanced user would have already done this as a part of their course , but still this was an interesting topi to cover and just so many peaple payed attention to the steps as they pointed out the possible mistakes

[@anishsarkar120]

this is taught almost anyone in engineering or in a technical field or last year of high school , i was first taught this technique in maths

[@KnakuanaRka]

A One big mistake that I think a lot of people have already noticed: you do not stop the algorithm the instant you find a path to the end. Instead, you just put the end node in the list and continue until you fully process the end note and put it in the discard. This is because the first path you find may not be the optimal one, especially when, as shown in the video, multiple partial paths exist with the same length so they could be processed in any order, so you need to keep working until you can be sure you’ve gotten all possible paths. For example, take a simple square with four nodes like this, with paths along the four edges with lengths as such: S-1-A | | 2 4 | | B-2-E In order to find the shortest path S to E, Dijkstra’s algorithm would start with this: S0 Ai Bi Ei First step is to process S; it has paths of 1to A and 2 to B, creating this: (S0) A1S B2S Ei Next is to process A, which has only one open path, of 4 to E for 4+1=5: (S0 A1S) B2S E5A Now as you described it, the algorithm would end immediately, with the path of SAE of length 5. But in fact, this path is obviously not optimal. In the correct algorithm, one would process B next, which has a path of length 2 to E for a lesser total of 4: (S0 A1S B2S) E4B Now you would process E, which had nothing to do, and now the algorithm would end and return the true shortest path of SBE length 4. Heck, your own video shows an example of why you need to do this. At the very start, you have a triangle with sides 7-3-2, and you note that the SA path of length 7 is left there until you process B, which gives you a shorter SBA math that overrides the other one. If E was at the other end of that 7 path instead of A, it would have returned immediately and ignored the shortcut!

[@Pheatrix]

You finished to early. There were still other nodes in the priority list that had a lower priority than 'E'. So it was still possible to find a shorter way! Djikstra's Algorithm terminates after the goal node has been processed, not when the first path has been found!

[@michaelpound9891]

Yep! Thanks for pointing this out, I spotted it too late :) I should have expanded d and f. Had there been a path from say d to e that could have changed things.

[@espinosaleal]

Hey Mike, what is the name of the C++ book behind you? Do I see the Elements of Statistical Learning as well there?

[@Super_Cool_Guy]

Melvin Klein C++ he needs vitamin C more like. ...

[@oahda]

If you're ever interested in getting back into it and want some less outdated material since C++ has been changing a lot in the last five years or so, I highly recommend Scott Meyer's 'Effective modern C++' (which presupposes a knowledge of older C++, however, but since you seemed to have that)! c:

[@daggawagga]

If you're into videos, CppCon has uploaded a great number of them over the last few years about almost any C++ topic you could imagine too. They're really nice especially for the modern examples.

[@minemaarten772]

Real Dijkstra's Algorithm implementations actually continue searching until the destination node E is at the top of the priority queue, as theoretically either from D or F there could be a path of weight < 1 to node E, leading to a shorter path than the found one of weight 7, in the situation at 8:31

[@TakanashiYuuji]

Yea, it's possible that there is, for instance, a faster path from G to E that passes through another node.

[@zamadatix]

A large number (most?) of practical implementations use integer weights disallowing 0 (which is equivalent to 2 nodes being the same node anyways). This allows a linear runtime complexity.

[@TakanashiYuuji]

Daniel Smith that seems like a rare edge case to me. If G-E was 3 instead there could still be a shorter path.

[@zamadatix]

Rare edge case for what in particular? Wanting a linear time guarantee with a simple solver? No, most paths are just ints because it's easier to deal with computatinoally and algorithmically. As for if G-E was 3 yes, there could still have been a shorter path. Same as if you had a different graph. Thing is he already checked the length from G->E and was likely under the assumption all weights are integers (partially because they all are, partially because he references "the implementation he knows" in networking at the beginning which is likely integer limited for the reason I mentioned.

[@isaacdouglas1119]

Yeah kind of annoying that they didn't show that and just stopped

[@philipkertsman1498]

This is awesome. I really like that you can feel the friendliness and good vibes between Dr. Pound and whoever is shooting the video. The energy passes through. This may seem immaterial, but this helped me engage and absorb more.

[@donniemorrow]

Dr Mike Pound is consistently making the content I've been enjoying the most on this channel. I'd love to see more videos with him

[@schogaia]

Dr Mike Pound just rocks!

[@mridulagarwal5881]

Before watching this video, I've always found myself confused regarding Dijkstra's implementation. This might just be the simplest and the best video for understanding how Dijkstra's algorithm works. Thank you very much!

[@kummer45]

This is a great start for videos of such high calliber. If something is deeply difficult should be precented like it is with all the difficulties that such topic has. This is what I call authenticity. If it is measure theory then everything should be explained in great detail WITHOUT ommiting difficulty. This guy gets it right.

[@thejimd]

Dr. Mike is my fav

[@matthijndijkstra25]

Ah, Dijkstra. What a lovely name.

[@Saltofreak123]

it just rolls of the tongue

[@IDixuu]

It does if you're Dutch. You can imagine "ij" being similar to "y"

[@matthijndijkstra25]

I know, I'm Dutch and my last name is Dijkstra. 😄

[@MAlgMAlg1]

That does not make it better in English...........

[@hiddeluchtenbelt6440]

Matthijn Dijkstra I imagined Dutch people chuckling in the background of this video.

[@gdfauxtrot]

My computer organization class will be discussing Dijkstra and priority queues soon, I feel like I just got an amazing head-start.

[@hellterminator]

In that case you better know there's a mistake in the video. Dijkstra's algorithm doesn't terminate until the destination node is at the top of the queue. The way Mike did it here, he found *a* path but *not* necessarily the *shortest* path. If for example the edge between g and e had weight of 14 or more, the shortest path would lead through k, but he wouldn't have found it. In this case Mike did get the shortest path, but he couldn't know that for sure before processing d and f.

[@TruthNerds]

Ironically, Dijkstra's algorithm as originally published in 1959 did not use a priority queue, and was asymptotically less efficient (quadratic run time). It took 25 years until Fredman & Tarjan published an upgraded version of it, with priority queue and an average O(n log n) run time.

[@dino130395]

In always enjoy watching Mike explain things! Nice video!

[@quarkyquasar893]

No, not my knee! -Dijkstra

[@yunusbahari]

Too much witcher detected

[@wesofx8148]

Pathfinding error.

[@dogemaester]

Dee-kstra or Dy-kstra?

[@Neoplasie1900]

@@dogemaester If you want to be closer to the original pronunciation, it would be Dee-kstra. Dy-kstra sounds more "englishified".

[@ghufranullah]

Please do A-star next!

[@siddharth_desai]

I'm pretty sure the end bit about the heuristics was leading into that, haha

[@EddieHart]

smash mouth? 😂

[@dbueno6375]

It's exactly dikstras but you have a heuristic that estimates the distance to the goal at each node. You add this heuristic to path length and that now becomes the priority. It's very very similar.

[@doubleru]

And then they'll get to the really pervy stuff, like customizable contraction hierarchies...

[@a.b.c.d.e...]

I have read and watched other stuff on this topic before, but I never felt like actually getting it. You know, when you understand something, but you still feel uncertain about whether you actually got it. Now I watched this and my mind is clear. I get it, it feels intuitive now. Thank you so so much!

[@danieldaniels1172]

I haven't enjoyed a presenter on computerphile this much since Tom Scott. A Dr. Mike Pound playlist should be a priority. He is excellent at explaining every topic I have watched so far. Thank you very much for the content guys.

[@snoopy1alpha]

Dijkstra, as I learned it, always searches the whole graph. What you presented is what I would call "A* with heuristic 0" (as you hinted in the final section). By searching the whole graph with the, lets call it "complete" Dijkstra, you are actually computing the shortest path to all vertices in that graph. If you start searching at your destination instead of your starting point, you get a data structure that contains the shortest paths from all vertices to your desired destination (assuming you reverse the path(s) from the result). Applied in a routing application (like a GPS system in your car), you do not have to recalculate the route if you took a wrong turn. For this approach being efficient, you would have to pre-calculate a sub-graph to run your Dijkstra on. For real map data you also want to take into account one-way roads and interpret them in reversed orientation. During my studies we actually did exactly that on a map of one of Germany's states. It was amazing. However, we did not do the sub-graph-part which would have allowed us a bigger map (all of Germany or even Europe).

[@PrimumGenus]

I asked for the English translation of another Dijkstra's Algorithm lecture video, and this is what I found. The explanation is a whole lot better.

[@stanleybacklund5614]

I love how a guest has never looked into the camera on this channel

[@hastley64]

they're all introverts.

[@Astral_Dusk]

This guy is way more informative than the 3min fuzzy barely audible whispering one that led me to an infinite path I'm still on for all eternity now.

[@konradd8545]

I just wanted to express my gratitude for the amazing work Computerphile is doing! I'm just going through Dijkstra's algorithm in my Discrete Mathematics course in uni and my lecture is utterly rubbish. Thanks to Computerphile video, I grasped the idea very quickly!

[@mehrosenasir3966]

The last part was amazing that dijkstra approach first consider the path with low cost no matter if they get you farther from the destination. So this is one disadvantage and also worth to mention that Dijkstra doesn’t work with negative weights. Perhaps I should say it works sometimes but not always.

[@stephenstringfellow1170]

I really wish this guy was a professor at my university when i was studying. very well explained and feels engaging.

[@alexanderzin]

Please, do some 3d graphics-related videos with Dr Mike Pound. I know there are already, but mr. Pound explains things so much better for me. Upvote if you agree

[@roleben3009]

This video was actually great, I perfectly understood how the algorithm works in a simple but nevertheless complex concept. One of the best explanations so far. Great video!

[@MistaMase102]

I got lost at S....

[@DanBowkley]

Spoken like a true satnav.....

[@saif0316]

Same

[@aurelia8028]

Are you proud of your lack of intelligence?

[@Pumbear]

Good job on the graphics. Made the video a lot clearer :)

[@jacobdavis000]

I found this video because I heard the name Dijkstra mentioned in another one of this channel's videos and wondered if it was the same person that invented the Shortest Path Algorithm. So I looked for this video to find out. Glad to find out *was* is what I wanted to see. IIRC: Dijkstra invented the algorithm to show how an early model mainframe computer can be used to solve the shortest path (traveling salesman?) problem. Don't know how accurately I remember it, but It's cool to find out that it is probably one of the oldest computer algorithms ever invented.

[@colin-campbell]

Witcher shoutout

[@DampeS8N]

Very nice lead in to A*'s heuristic at the end, but I wish you'd called it out specifically there so the interested could go out and learn the next step themselves. (though you did mention it in the video which is good)

[@shukaizhang2850]

Definition of Recursion in the dictionary: See "Recursion"

[@nq2c]

error - maximum recursion depth reached

[@Zmunk19]

if you google "recursion", it says "did you mean recursion?"

[@MS-il3ht]

@@Zmunk19 you're right :-)

[@Yoshi-jr6zn]

@@Zmunk19 wow, i tried this

[@ansismaleckis1296]

Why use recursion when you can easily get away with loops and stack? In most cases recursion is more "expensive" than itteration.

[@johnschultz4345]

Very nice (other than the termination goof up). One thing I wish you had stated more explicitly is exactly why Dijkstra continues to go down the closest/cheapest paths to the finished set: because there can be no shorter path to those nodes from the source.

[@JohnzillaTheHun]

I was born in the US and my last name is Dijkstra. I majored in computer science before I ended up having to drop out. A few of my professors got excited when taking roll-call, and I had to explain to them that Dijkstra is like the “Smith” of the Netherlands from what I’ve been told. I think I might be related to him though! Just because I’m always trying to figure out the easiest way out of every situation

[@joemarriage3002]

Merry AoC day 15, pathfinders!

[@fly7188]

Pathfinding algorithms always get referenced in the context of spaces and distances but its just as effective when dealing with abstract spaces, ones with dimensions that are defined manually. I imagine there are many problems that could be posed in the context of an abstract space that could be solved with these sorts of algorithms.

[@hil449]

Dynamic programming problems comes to mind

[@CuriousAnonDev]

the last part was just amazing dude! no way i could have found out the that problem/situation on my own

[@dougie8747]

Game developer here, I'd consider Dijkstra's (perhaps more A* but Dijkstra's is perfectly sufficient for small graphs) to be one of the core algorithms that everyone should know. Please do a video on Prim's (or one of the other MST algorithms) as well, my favourite algorithm, after Quicksort of course. :D

[@atulkoshta641]

What a lovely explanation Dr. Mike!

[@leonhrad]

You made a small mistake. The algorithm terminates once you pop the end node 'E' from the priority queue, because that's when you know that you've found the shortest path to that node. You shouldn't terminate as soon as you've found only one path to the goal.

[@philipbotha6718]

The algorithm should terminate in this case because the cumulative cost for all the other paths were already higher than the current path. If you had negative costs, then I believe you should only terminate once 'E" is popped.

[@bradezard1581]

No, D and F were still on the queue with 6 and E had 7. The path was ultimately the right one, but you can't guarantee that unless you wait until actually popping the goal node. If D or F had a path cost

[@tombrady7390]

they were just trying to build a overview for the algorithm rather than a comprehensive explanation which i think they did

[@hil449]

@@philipbotha6718 Dijkstra doesn't work for negative weights

[@atulkoshta641]

This guy is always wonderful to hear. Thanks, Dr. Mike :)

[@shelbycollins6116]

There must be something off with me watching this on my free time on a holiday and enjoying this more than movies or shows

[@Mrslandshark]

This is brilliant for Decision 1 revision for Further Maths!

[@Ericnorify]

That ending seems to be tease for an upcoming A* video! Looking forward to it.

[@TechXSoftware]

I am using this for my games, it is quite complicated then it seems. Its stats basically. I like this algorithm, its so much faster saving CPU power.

[@ZomB1986]

I like the pace of this video. They are usually much lower paced.

[@socksincrocks4421]

Dr. Pound should have his own channel. My new favorite youtube video series after PBS SPACE TIME and EEVBlog.

[@Richardincancale]

There's a related algorithm called Floyd's algorithm that calculates the shortest path between all nodes in a network, not just two points, that is used in practice for network design, routing etc.

[@code-dredd]

It's been over a year now. I'd like to see the foreshadowed sequel to this video.

[@highlewelt9471]

Just yesterday I wondered about the travelling salesman problem and path finding and now you upload this video

[@MrJjjakey]

This was on my final a few weeks ago.

[@Sharpienero]

Same. Algorithms class was super fun.

[@MrJjjakey]

Mine was Networking, before that I had the algorithm on a CS based Mathematics final the year before.

[@TheThunderSpirit]

great. would love to see more videos on different type of algorithms.

[@elysweetmemory]

Thanks for the wonderful explanation and the short bit about its downfalls!

[@TransparentLabyrinth]

I feel like pathfinding algorithms make less sense the more explanations I watch of them. T_T

[@vedangfate6290]

I feel you T-T

[@__-yz1ob]

T-T

[@user-rf4vc7mt4d]

T_T

[@albertomedinarobredo]

Computerphile and sleaford mods, Nottingham gets half of my KZbin visits

[@nemoalvaradoTV]

Just want to say thanks for the sweet explanation on this algorithm. Couldn't learn it at school lectures but you made it clear.

[@SakuraxStars]

Super interesting example of how Dijkstra might be inefficient at the end!

[@a9raag]

Thank you for correctly pronouncing Dijkstra sick of people calling him DJextra

[@HiAndHello-w9l]

doing Dijkstra’s Algorithm right now for an assignment... now to tern this into code

[@kostyapesterew1068]

wait why was the search terminated after we found 1st route to end point? isn't it possible that last segment is huge and it isn't the shortest way?

[@_aullik]

Cause he messed up :D look at 8:20 The pile at the right is your priority queue. You only ever work at the top most element of this queue. The Q is ordered by distance. The mistake they made is that the put "e" at the top of the Q. It should be below "f" tho. This means they would have had to check "d" and "f" first, then go and check "e". Checking "e" means you've finished the algorythm.

[@Pheatrix]

It shouldn't have been terminated. Normally the search gets terminated when the goal is in the top of the priority list. They seem to have forgotten that.

[@shadowmil]

Because you sorted the nodes you were checking by the cost of getting to that node. Meaning you know that any other paths that might exist will have a higher cost.

[@_aullik]

read my answer. they messed up.

[@rawrnomnomnomgrrrrrr]

From what I can see, the routes that went down the roads to the right were both sitting at a value of 9. Since we had already found a path to E that was 7 which is < 9, then the search is stopped for all routes that have a current value > 7. In a larger implementation of this algorithm, after a route to the destination is found, then any routes that are currently being searched are discarded if the current value is greater than the best route, as they cannot be the correct answer. (Note: I might be getting this part confused with dynamic programming, but it seems to me that they are essentially the same thing based on this simple example).

[@DepressedNOF]

Well with the A* you don't have the problem with going in the wrong direction for too long (still possible for a while) because you will keep the realworld distance in your heuristic function. And one more thing, correct me if I'm wrong with this, but to be sure about that the found rout from S to E is indeed the shortest you would have to continue Dijakstra until every node is finished. So you can't stop when you found one route from S to E like in the example. In A* you can stop then.

[@RedHeroe1]

i just love computers some videos i don't understand a single thing but i love this channel

[@bombrman1994]

Education systems are using these public videos what a great time to be alive.

[@gradientO]

What?

[@bombrman1994]

@@gradientO ?

[@biswajitsingh8790]

damn this guy is a legend for explaining it in such a simple manner.

[@ahnafs8930]

just looking at some concepts ill face as a cs student (still in high school), I'm starting to reconsider my options

[@KabyAlkaris]

Who else is dutch? Netherlands, represent! Dijkstra mah boii!

[@jopiekiller]

KabyAlkaris aiiiii

[@McKon.]

I had no idea he was saying Dijkstra until I saw the intro.

[@justinward3679]

KabyAlkaris No one cares, go back to your shunting yard.

[@AhsimNreiziev]

Dutchman here! So very proud of Dijkstra whenever he and his Algorithm come up.

[@JohnathanGross]

The final step is wrong. You can't be sure that the first node to reach the destination is the shortest. What if instead of 2, the path from g to e was 100? It would still be the first to reach it, but would be far from the most efficient. You have to put e in the correct position in the priorities, and only when all shorter paths have been exhausted can you be sure it's the shortest path.

[@StockDC2]

Great explanation. One thing though that would have been nice would have been if you guys showed the weight of all the edges instead of just the edges that a particular node is connected to.

[@perfectlyfantastic]

very informative , it was like the movie finished in between , it would be lovely to check the second part for the limitations of Dijkstra's Algorithm

[@mavil64]

So it is just like an upgraded bfs through a graph? That seems such an easy logical next step to make. I wish I 've seen this video before finishing my college assignment.. It would have been a very cool project.

[@anetakahleova5705]

I love you Dr Mike Pound!

[@j7ndominica051]

I wanted Euro Truck Simulator to implement a "penalty" for road sections, to stop it from sending us through gas stations and too many junctions, but I didn't realize this was part of the standard way of route planning. I suppose going through a node should also have a cost, if it means slowing down to turn or going through a city.

[@j.heights3190]

haha

[@dbsz]

It would be a lot easier to just part the node into two and put an edge (road) between the two representing the slowing down. That is probably how it would be done as you wouldn't have to rewrite the algorithm, just adjust the graph :)

[@SHYBMX]

When I was taught this; it was done in a table instead of a list, which in my opinion is easier to understand.

[@umchoyka]

I think you missed a crucial part near the end. You don't stop the algorithm as soon as you hit E. You only stop once E bubbles to the top of the sorted list, otherwise you might miss out on a faster pathway. For example if the connection from G to E had been a very large number, say 100, then the path going to the right would have been faster even though you got to E through G first.

[@robertbush8170]

One note here: the implementation was slightly incorrect. To be assured a path is minimal, we need to "visit" the endpoint first, not just assign a distance. There were a few vertices before e in the priority queue which needed to be visited first. We can be assured no shorter path exists (in a positively weighted graph) after visiting e since any other path from another vertex would extend the distance from that vertex which - since e is first in the queue - will be greater.

[@siprus]

In Dijstra smaller can be better, but it also work with larger numbers being better. You just can't have any negative numbers. Also you need the nodes in order where there is shortest dinstance to! You can't just decided that you've got shortest route to final node, just because you found a route to final node!

[@MrNdb10]

I enjoy seeing my discrete math class coming into use!

[@sporkafife]

Hey! I remember Dijkstra's algorithm from A level further maths! Back then I remember it being more complicated... seems really simple now...

[@JBinero]

What if the last weight was 10,000? Wouldn't it pick that as the fastest route then, despite it being much, much slower than by going through L?

[@Simon-nx8hq]

Jeroen Bollen Yeah, actually the algorithm only terminates, when the destination node is finally processed, because that means that it is the unprocessed node with the shortest path to it and there cannot be a shorter path. They kind of messed up in the video.

[@TheSlimyDog]

Another thing this missed was the fact that when Dijkstra's algorithm terminates, it will find the shortest path to all vertices in the graph from that starting point.

[@rmsgrey]

+TheSlimyDog That depends whether you terminate when you process E (as they should have) or continue until you have processed all nodes. If you're looking for routes from London to Dover, you probably don't care about the best route to Edinburgh. What Dijkstra's algorithm does give you is the best route to any processed node - your destination and anywhere cheaper to reach.

[@TheSlimyDog]

I'm sorry, that's correct. You can stop once E is at the top of your priority queue.

[@rmsgrey]

I should have mentioned earlier that, when deploying it "for real", Djikstra's algorithm is usually run until every available node has been processed, rather than terminating once you reach a designated destination simply because it is so easy to upgrade to A* and it offers such an improvement in performance if you do have a destination to aim for.

[@alcesmir]

Nice walkthrough of the algorithm, ignoring the fact that the algorithm was terminated too early.

[@Rouliousin]

It is interesting but you obtain the shortest road between two nodes only !!! You could solve that problem by rasterizing the road network and then calculate the accessibility of each point by using propagation algorithm in cost/friction surfaces.

[@AnkushPuriSDE]

Thank you for this! Made it so simple to understand this algorithm!

[@1flybyguy]

Thumbs up for pronouncing the letter h properly.

[@ROBLOXowns]

What you should check if you understood after watching this, is why you don't have to visit all the nodes and yet you've found the shortest path.

[@vultoneo]

I think a mistake was made @8:30. E is put at the top of the priority list while there where there might still have been some faster routes (via d/f, as their "values" are currently lower than the "value" to travel via G). If the value of edge GE was for example 20, the current method would give an invalid result.

[@F1refoux]

I wish my teacher explained Dijstra's Algorithm with such clarity... Thanks for this great explanation !

[@ManuTheGreat79]

Thanks, this is useful. I was thinking of solving the routing of a metro plan (finding the shortest path for a non existing "this should be the Brussels metro" plan) (website with Google Maps), using Dijkstra.

[@Ramiprops]

What if the last section from G to E had a weight of a million? That wouldn't be the shortest path!

[@Pheatrix]

That's the reason the algorithm normally terminates when the goal is on top of the priority list. Seems like they made a mistake.

[@Zahlenteufel1]

if that was the case, e would go at the bottom of the queue because it had a million assigned to it and then it would check the other nodes that are above in the list

[@sbkpilot1]

you eliminated C when it had the same cost (3) as S > B > H, however what if C connected to E with a cost of 1? Then S > C > E = 4 would've been the shortest path not S > B > H > G > E

[@Spasmomen]

I recently learned about this when I was investigating whether I could calculate the longest route, as in most distance, within a set time. I'm trying to do this with networkx in Python, following some tutorial I found online. All tutorials though focus on the shortest path, where I want the longest path possible within 8 hours. I haven't figured out yet how to do that. I think I need to use the Chinese Postman Problem, but not sure...

[@netbotcl586]

The longest distance problem is reduced to the travelling salesman problem, so I don't think possible in polynomial time.

[@starchar9378]

I liked this video, I have to tutor this algorithm and this gives me a nice cheeky way to explain it. Thank you.

[@joeytje50]

What I don't understand is: if G had another route to E. So: there's a G->E of length 5, and a G->X->E of lengths 2 and 1. Then after looking at just G, you'll think "I've reached E, I'm done", but if you would look one (or perhaps more) steps further, you'll find that the route through X would be shorter. This is not handled in this video.

[@hamzanasir1590]

Great Explanation Ever Sir 👍👍👍

[@patrickjoel8779]

This guy is brilliant

[@udimatalon1367]

the path to e is only guaranteed to be the shortest one if you put it in it's rightful place in the queue and go on until you reach it.

[@vedantbhardwaj4058]

Wish this guy would be my professor for Data Structures and Algorithms

[@fisslewine1222]

I'm really liking your tutorials; but would love to see some code as well!

[@Maaruks]

this is the best explanation

[@JDines]

While a router can use OSPF to determine which next hop to send the packet there is no guarantee the path calculated by source router will be the actual path the packet takes.