Dijkstra's Algorithm - Computerphile

Dijkstra's Algorithm finds the shortest path between two points. Dr Mike Pound explains how it works.

This video was filmed and edited by Sean Riley.

[TheRoboticLlama]

To understand recursion, one must first understand recursion.

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

[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!

[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!

[minemaarten]

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

[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

[philipkertsman]

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.

[dino]

In always enjoy watching Mike explain things! Nice video!

[mridulagarwal]

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!

[danieldaniels]

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.

[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!

[stanleybacklund]

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

[roleben]

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!

[konradd]

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!

[atulkoshta]

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

[kummer]

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.

[Pumbear]

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

[stephenstringfellow]

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

[TheThunderSpirit]

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

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