8
Sep

# Dijkstra’s Algorithm – Computerphile

• Joel Leung says:

Is it possible to have an unordered list or a list that isn't a priority queue but instead whenever assigning which node we are going to evaluate now (or the current node), could I just use a for loop and iterate until I find the node in the list with the lowest cost and evaluate that node?

• Wandering Soul says:

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

• Mark Freeman says:

LOVE THIS CHANNEL!!!

• ROBLOXowns Productions says:

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.

• Peter Edwards says:

I thought Dijkstra's Algorithm and others were more researched in path finding for games.

• triton62674 says:

10 too little frames to watch this video.
For shame.

• 3st says:

4:54 lole

• Aleksandr Hovhannisyan says:

Why is Dijkstra's algorithm smart, though? Aren't we visiting all possible vertices either way, regardless of whether we examine freeways or residential streets first, for example?

• Michał Gołuński says:

I think there is a slight mistake in this explaination. When we get to E we actually don't know that it's the shortest path UNTIL we check all other that are shorter. In example from this video, IF there was a path from D to E with weigth 0, it would actually make S-E route faster.

• Loosa Bway says:

Enthusiastic, Knows his stuff I’m sure. But no teacher. Sorry.

• Maaruks says:

this is the best explanation

• Mohamed Abdelaziz says:

more than amazing

• Billy Armfield says:

why would you search all the adjacent vertices of B before checking C (last remaining adjacent vertex of S)?

• RedMikePumpkin says:

Bs = 2 =DChcSEwjUgeGRr5nRAhUetsAKHcBpALUYABAR&sig

• First Last says:

This guy really grew on me.

• Mason Pickering says:

You can find Dijkstra in the bath house in Novigrad

• Source Intelligentsia says:

• Siva Prakash says:

Mike rocks. Please do lot more videos

• José Almeida says:

How can i predict the direction of the path to avoid the last problem?

• Wen Chu says:

chaotic explanation !

• bigcheesetaste says:

Could it be, maybe, Dijkstra's final aeon?

• Tunturisorsa says:

well doesn't this video come at a handy time

• benny b says:

• Maximilian Faust says:

some quick maths

• DepressedNOF says:

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.

• HitmanBobina47 says:

Did mike's face get borked?

• Q Squared says:

TIL OSPF is a dijkstra algorithm

• Ahanaf Rakin says:

• - _ LIR _ - says:

How to implement infinity in c++ ?

• Akshay Sapra says:

at 5:01, shouldnt C be brought to the 2nd top because its a priority queue?

• Yashsvi Dixit says:

I was like Mike Pound but then I joined college and every brain activity just died

• Udi Matalon says:

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.

• Pankaj Kumar says:

the guy is smart.

• Ben Trono says:

This is a great video, but technically this algorithm would continue to run until E is removed from the queue, rather than stopping once E is assigned its first distance. The Algorithm would remove/visit nodes D and F, and then finally E.

(to anyone just learning) There are cases where the first distance assigned to E is not the shortest, like if this same graph was manipulated to have an edge from G to E worth 3 instead of 2, and an edge from F to E worth 1. But once E has the shortest distance in the queue, it is guaranteed that the shortest path to E has been found.

• Marc Grec says:

What is the difference between Lee's Algorithm and this one?

• Ege Ersü says:

Why didn't you just associate the numbers with distances? Would have been much easier.

• Ege Ersü says:

When he is refering to things on the graph, it doesn't make any sense to cut to his face. We need to see the nodes and edges he is talking about.

• Saurabh Moharir says:

Smart Man!!

• __ says:

lol hokkams razor in algorithm form xD

• ItTakesOne ToCatchOne says:

I think that some clarifications (annotations or something like that) should be made with regards to the erroneous implementation.

• Atul Koshta says:

What a lovely explanation Dr. Mike!

• Akasuki says:

1080p50 is butter.

• a8lg6p says:

Where do they the printer paper from? I remember that stuff from when I was a kid.I didn't know it was still made anymore.

• Pr1celess Path says:

First time I saw your videos lol you are like Dan Brown the NLP (Neuro Linguistic Programming) expert who could ask you for directions (likely to a place nearby that he knows damn well already how to get there) simultaneously using body movements of need vs charity insinuates using non-verbal means of convincing you that you should give him your wallet because he was in need that you held his water as a favor. How the water, the wallet and asking for directions to the library are related, is even more baffling that he was able to succeddfully pull it off without fail 3 times in a row the 3rd attempt the more amazing. His explaination of why you hand the wallet over to him is mixing math, science, misdirection, sleights, slight of hand (gypsy theif), combined with psychology, sociology, and communication devices (metaphors, alliteration, and creative entertaining sentence patterning) to be dazzle you into appreciating him rather than the reason he has approached you: TO TRICK YOU. Look that guy up he is the splitting image of you.

• Tamir Cohen says:

Wouldn't you multiply the actual distance in KM to a junction by the difficulty to travel there to get an accurate number telling you the "cost" to travel to that junction?

• byron perez says:

allways amazed when someone explains computer science without a computer

Has the traveling salesman problem been solved yet?

• Grant Bowen says:

Dijkstra… Witchering intensifies

• code_dredd says:

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

• TransparentLabyrinth says:

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

• kon kos says:

you should really do more pathfinding algorothms like bfs dfs primm etc

• LBGST zockt says:

I understood some of thoose words…

• Mike West says:

I can't follow the diagram because whomever edited this video felt they need to keep cutting back and forth to his face. The result is very confusing and hard to follow

• Theodore Tang says:

Wow, you are sooooo cool. Thanks for your video!!!

• Keith Desouza says:

Nicely explained. There is still something confusing. The overloaded use of the numbers between the nodes. Is that number, the weight (speed) of the road or is it the distance between nodes?

• Bikal says:

50 fps gang

• Tashlif says:

gettt intoo the pointtt maaannn you speakk soo muchh

• sting281 says:

One of the best algorithms ever. Respect, respect and only respect.

• Philip Kertsman says:

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.

• Skyy 95 says:

♥♥♥

• Flux Capacitor says:

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

• Dr. Harish Ravi says:

Great demonstration, thanks a lot!

• SandroRocchi says:

Dr Mike eyeballed that neither I or J would get to E faster than G, and skipped to the end when an algorithm would not have been able to, without knowing the cost of getting to K. In this example we're talking about moving in the physical world, but most of the things we use shortest paths algorithms for can actually have a negative weight, so if we had a -100 cost between J and K, that path would be so fast we'd arrive there before we even left, and Dr. Mike refused to discover time travelling. Jokes aside: this algorithm isn't finished before you know the cost of arriving at every node in the graph.

• LIKE YOU IAM says:

finally an approach that takes into account the practical implementation. Thanks for mentioning the "priority queue"!
One quesion is still left for me: WHERE is the algorithm running? Is it always running at 's' and the priority queue gets updates from the other nodes? Or is the priority queue copied to other nodes?
I guess both would be possible, the former probably being easier to implement

• Tijs Perdaems says:

As a Dutchie, I like your pronounciation of Dijkstra xD

• Joseph Peters says:

He messes with alot of stuff

• Mum Blic says:

Nice to see that my own created algorithm is similar, … well exactly the same and it has even a name ;-))

• Jean-Nay Mar says:

Right ?

Frodo is trying to find shortest path to Mordor, sneaky hobbitses!

• Ahmed Yassien says:

OMG i love this guy,i love this channel i missed my lecture where the Dr explained it and by all means i don't think he could've explained it better thanks <3

• Samah Samiee says:

How are those numbers even decided?.?

• Mihaela Costea says:

how come you jumped from C to H?

• Dave J says:

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.

• Rasyid Al Faruqi says:

his voice really fits to teach

• Nathan Patera says:

-1, disliked for too much camera jumping. Hard to focus when I keep seeing different camera angles. Good content though, but not worth the pain of watching…

• Jim Giant says:

6:58 The virgin A* vs Chad Dijkstra's Algorithm

• Zaid Khan says:

The last part is worth the mistake he made about the recursion ending abruptly.

• The Wiedźmin says:

Now how the hell am I supposed to code this algorithm ?!

• The Wiedźmin says:

I taught Dijkstra was in the Witcher universe and not a real man solving math problems…

• Joe Stevenson says:

so the prioty queue would be a heap, right?

• Razman Sarit says:

You know what dude, you're like Jamie Oliver, but with complex algorithms

• Raymond says:

• Stanley Backlund says:

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

• the one who never gave up says:

he is in my age and he has a PhD while this is my first year sc engineering and barely gonna make it ,jez i wish i never was born.

• Apro Dan says:

Does anyone know a method to get to the endpoint even if almost all nodes are intertwined? I feel like using cards would take forever. So what else could we use?

• Sinan Akkoyun says:

We're all here for Pathfinder

• Marco Aurélio Lima do Nascimento Junior says:

wow, really interesting

• Endrit Shabani says:

I always thought Dijkstra was an Indian xD

• Recycle Bin says:

how to win at flow free

TIL how to Djikstra is pronounced, my Indian professors sounds completely different. Still having trouble speaking that word.

• Арсений Буров says:

This is my favorite guy of them all! Thanks for the content!

• Keshav Sharma says:

Dijkstra's Algorithm finds the shortest path between two points X
well the above statement is not really correct,
its a single-source shortest path algorithm and so given some vertex/node V, it finds shortest distance from V to all other nodes in the graph.

• Nate Higgers says:

Pathfinding in minecraft is very important

• Ben Jordan says:

How do you calculate the numbers between the paths in real world navigation like an OpenStreetMap service? You explained that it is not exactly the distance between two points, but more the "difficulty" of a road. But do you take the distance then and multiply it by a difficulty factor (eg. 1 for highway and 2 for small road with a speed limit of 65 km/h 2 times lower than the estimated speed of the car driving on the highway without speed limit = 130km/h)?

• M Neztsosie says:

I suppose this is used for cell towers taking into account var

• LivingBlast, LLC says:

I'm seriously convince that dry-erase boards have not been discovered in the UK

• JDines says:

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.

• Chandra Chud says:

Great way to explain it.

• dubstep1994 says:

Maybe he should re record it in a much simpler way. And with correct line distances according to time it takes to travel the distance. Too much noise.

• Snoopy1alpha says:

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