A Guide to Dijkstra's Algorithm: Best-Path Finding Part 1
Вставка
- Опубліковано 9 січ 2020
- Ever wanted to know the fastest way to get somewhere, but Apple Maps keeps telling you to drive off of a cliff? Here's how to do it yourself... For just how the algorithm works: skip to 2:56!
Part 2, which will cover the black magics of A* search, is here! • A Guide to A* Search: ...
Let me know in the comments if there's any other algorithms/concepts I should cover!
Facebook: / llamaexplains
Play around in this awesome path-finding comparison site here: qiao.github.io/PathFinding.js...
Pseudocode for Dijkstra's:
S = start node
S.path = S
Add S to frontier
Repeat:
Remove node N with smallest cost C from frontier
Add N to explored
If isEnd(N) : return N.path
For each edge E of N:
Get adjacent node N’
If N’ not already in explored:
N’.path = N.path + N’
Update frontier with N’ which has cost C+E.cost
wait why is this video so high quality easiest subsribe of my life
:D
I agree
Thanks for the amazing comments y'all! Really appreciate the support. Next video's coming out within a week, thanks to the quarantine and being forcibly locked in and stuff. haha jk this has changed my behavior in no way whatsoever but really new video soon
You're basically Casually Explained, but high quality educational content. I hope you keep this up, because I want to be able to brag that I was one of your first 500 subscribers.
Thank you! :)
Very interesting! Spotted this on Reddit and had to check it out. Thanks for your time and effort! :)
Good work, waiting for more content!
This was beautiful , underrated channel ,great job !!!!
I don't get the joke about fluffy camels doing math. Llamas are fluffy camelids, but that's you.
happy to learn this way!
Well explained bro thx ❤️
The USC joke got me good. Well done!
good job bro
Please post more graphic theory videos also, would inspire the fluffy camels to learn math maybe.
smasheddd the subscribe button
Why at 4:04 isn't "AB:10" removed from the frontier since "ADB:7" is a better path to the same node? Is it simply because the algorithm never removes *anything* from the frontier?
Yep, the algorithm works the same way if you remove known suboptimal paths from the frontier or not. I choose not to do it because it's simpler, but if you implement it the other way it will also work
Thaaaanks , But, How to apply Dijkstra Algorithm to Google Maps ???
blockchain LUL. When you watch 10 seconds and he already fucks up big time.