Pathfinding algorithm comparison: Dijkstra's vs. A* (A-Star)
HTML-код
- Опубликовано: 8 сен 2024
- Language: Python
Data: OpenStreetMap
Library: OSMnx
Visualization: Blender Python API
NOTE: We programmed A* using a Greedy-Best-First Search Logic, as opposed to implementing a heuristics function. Because our A* search only considers Euclidean distance to the target, it will not guarantee the shortest path when presented with obstacles.
Finding a path faster isn't faster if the path it finds isn't faster than the faster found path.
this is a sentence
Shouldnt this be "Finding a path faster isn't faster if the path it finds isn't faster than the *slower* found path." or am I misunderstanding?
@@Me1lethe slower path u r referring can be hold as reference path , same as guy is saying it’s just faster , the word faster or slower is just a reference to what u r saying 😂😂😅
en.wikipedia.org/wiki/A*_search_algorithm#Optimality_and_consistency
With an appropriate heuristic (in all but pathological cases) A* will not only be faster than Dijkstra's algorithm for point to point traversal, but it will also produce an optimal result.
Worth noting is that although Dijkstra's algorithm was designed for point to point mapping, it's a poor choice for that use case - it's a far better fit when you're seeking to calculate path lengths for all possible node pairs in the graph.
It all depends on the user. If only the user will be as logical as you...
A* with proper heuristics guarantee shortest path
Dijkstra and A* should return same length best path
Both examples show that A* implemented incorrectly
Having inaccurate heuristics is not necessarily a sign of "incorrect" implementation. You cannot always have a perfect distance estimation function without significantly increasing the overall calculation time. With a homogenous grid it's super easy, but if you're working with city streets and potentially traffic data for those streets, there's no way to quickly calculate an accurate distance estimation. A* can still be useful for finding a good path fast, even if it can't guarantee the best one in these situations.
@@NihongoWakannaiIf the heuristics work s.t. they always cover the best case and no real route can be found which is better than heuristics then yes, A* DOES return the optimal path. A* is used in navigation through cities all the time. Or do you really think your GPS calculates through all the streets in your city? With pathfinding in cities, A* is guaranteed to return the shortest path, no matter how inhomogenous the roads are, if it uses proper heuristics. Virdvird is right, you are wrong.
@@LarryMcLarren Not with the same speed benefits, when you have to be so pessimistic with the heuristics the calculation time approaches a basic Dijkstra. There are applications where the speed of calculation is more important than the accuracy of the result, that is not an "incorrect" implementation, it's a cost benefit analysis.
@@NihongoWakannai What you say is generally true, but not in cities as cities do have speedlimits. actually, besides Germany, almost any country has speedlimits and you have a v_max to calculate your optimistic heuristic with. As I said, when navigating through cities, there ALWAYS is a heuristic to find the optimal route regarding driving distance or driving time. In general, you of course are right: If you want to find the cheapest train route, an optimal A* would be Dijkstra, as the only heuristic to be better or equal to each best price is 0.
No heuristic is about guarantees
> We programmed A* using a Greedy-Best-First Search Logic
just fyi, this means you did not program A*, you programmed a greedy-best-first search. A* is by definition not greedy
A* algorithm always finds shortest path with correct heuristics function.
It doesn't matter what heuristic you use. A* guarantees the optimal path.
@@blissful4992This is not true. If the heuristic function over estimates the cost of a connection A* can terminate early with a sub optimal path. An optimal path can only be guaranteed if the heuristic function is admissible for a given problem.
@@IceTank If the heuristic is non admissible (which is what you are explaining) we don’t refer to it as Algorithm A-star, we refer to it as Algorithm A. A-star is a subset of A with an admissible heuristic.
@@blissful4992exactly 💯
If it doesnt find the shortest path youve implemented A* algorithm wrong. A* algorithm guarantees the shortest path between 2 points.
Hey thanks for the comment! I updated the video description with a short explanation of A*'s behavior in our implementation. Hopefully it clears things up!
@@anthonymadorsky1551I appreciate the effort but there is a certain level of changes after which an algorithm starts being a completely different algorithm. Your algorithm is not an A* algorithm since for each potential node A* requires to evaluate both passed distance and estimated distance using a heuristic function which is usually simply euclidian distance. It seems from the video you are only evaluating estimated euclidian distance.
This is content stolen from another channel, so the poster likely has no idea what they’re talking about.
@@dhess34 The content you see is 100% our own. This is my group's final project submission for Data Structures and Algorithms. We are second year computer science students who were asked to create a visualization for, and compare two algorithms that accomplish the same task. Please reach out if you have any questions!
@@anthonymadorsky1551source code? or your claim is wrong
Nice video, even though its not really a fair race since dijkstra needs no information about the location of the goal but a* does. They are not built to solve the same problem but rather for different scenarios
A* doesn't necessarily need the location of the goal. You are referring to a specific heuristic (that calculates distance for example) used in tandem with A*.
Dijkstra is A* with a uniform heuristic.
A* is Dijkstra with admissible heuristics.
@@blissful4992 and what do you think is needed by the heuristic used by A* to calculate distance? exactly, an information about the location of the goal (e.g. coordinates) just like the commenter said.
@@zeroanims4113 Please go educate yourself on A-star. Distance isn’t necessarily required to make a heuristic for A-star. In a map application scenario you can use: road length, traffic, steepness, narrowness, among other things. A-star doesn’t calculate distance by default. It’s the addition of a heuristic that allows it to do so.
@@blissful4992 and isn't road length, traffic, steepness, narrowness, etc... an extra information required by a*? that's the point of the original comment, and my reply is just another example of extra information a* might use (distance). Again, the only point we're making here is that dijkstra uses no other information, but a* does. Do you agree?
@@zeroanims4113 No, it’s not required by A*. Actually if you give a heuristic of a constant value to A-star it behaves exactly like Dijkstra. That’s the point and it’s why you’re wrong. Sorry. A-star doesn’t need extra information, it just performs better with it.
You either clearly didn't understand A* or you applied a heuristic that could be greater than the path length(e.g. Manhattan Norm) if you would've applied Euclidean Norm(a heuristic that is always smaller than the length of the shortest path between two points) for example, then a correct implementation would've guaranteed shortest path(equal in length to Dijkstra's)
both may seem viable in this exemple, Dijkstra's may even look better because a few seconds more of calculation might saves you minutes of driving. However keep in mind how they both scale, Djikstra's is kinda like a O(n^2) algorithm while a* is more similar to a O(log(n)) algorithm, if you attempt Dijkstra's algorithm to google map for finding paths across multiple countries or even a few dozen kilometers, you'll soon find out it will take longer to run than you trying to run to the destination by feet...
So yeah it would've been fun to add a visualisation of this scaling but it's still a very interesting video, thanks :)
big joe notation
no they just fucked up and did not implement A*, else it should return the shortest path
@@minutenreis idk, a* is a middle ground beetween Dijkstra's and greedy search, you can adjust the heuristics to fit your needs.
(but I agree that the "basic" a* do the same result as Djikstra's for a significantly decreased complexity)
@@minutenreis A* only returns the shortest path guaranteed if you have a 100% accurate distance estimation to the goal. That is not possible here without a very expensive pre-processing step.
@@NihongoWakannai finally, they come to speak the facts and save the day. I absolutely love how others are saying "just use correct heuristics", leaving the details of "correctness" behind the door. The "correct" heuristics here is a giant lookup table with which you won't even need the algorithm in the first place.
I love watching these types of videos :D
As others said: That's not A* ... you should change the video title before other people get things as wrong as you about those algorithms.
The visualization is cool though ;)
So what you're saying is you implemented A* incorrectly?
ya the path should be identical if they both found the shortest right ?
I came here because the thumbnail of the video looked like the embryo fetus of the xenomorph alien.
I was thoroughly disappointed.
Then I read the title of the video.
Now I am thoroughly impressed!
Dijkstra's algorithm looks like how a slime mold navigates toward food.
Those algos might seem similar to unexperienced programmers, but they are diffirent things and serve diffirent purposes.
A* is a pathfinding algorithm and Djkstra is a mapping algorithm. Therefore it processes much more data than A* given the same dataset.
For example, in a game, use djkstra to map information on the game envirnoment for AI, and use A* for player controlled entities.
No. A* is an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.
@@blissful4992 I think you misunderstood the guy you replied to. Dijkstra isn't about finding the fastest path. It's about generating a map of all pathes to all possible destinations. If you use A* to map, that map would be incomplete as pathes that won't lead to your destination will not be further investigated.
So you use A* if you know where you want to go and just want the fastest path and Dijkstra to get an idea of everywhere you could be going.
For example in a game that simulates tactical combat of ranged units there are a lot of aspects of how to evaluate the usefulness of a specific tile. I want to compare all of my options and thus also need the path-length to all of them. Dijkstra populates the pathing-distances for every single tile of my game-map with a single function-call.
@@ailst False. The entire point of the Dijkstra algorithm is finding the shortest path between two nodes in a weighted graph. E. W. Dijkstra outlined this when he published his algorithm in "A note on two problems in connexion with graphs" in Numerische Mathematik. Its the entire point of Dijkstra's algorithm, the A algorithm, and A-star algorithm. Your statement is completely deranged. Dijkstra's algorithm comes from a solution proposed to the second problem in his article "Problem 2. Find the path of minimum total length between two given nodes P and Q [in a weighted graph]."Numerische Mathematik l, 269- 27I (l 959)
Furthermore Dijkstra's algorithm and the A* algorithm both guarantee finding the shortest path (A* depending on the heuristic). The A algorithm however does not. A* is a variation of the A algorithm where h(n)
Code please ???
Dijkstra: The evil empire is hunting for you.
A*: The evil empire is hunting for you - and they have spies everywhere.
I don’t know if it’s really a proper pathfinding algorithm if it doesn’t find the shortest path.
Dijkstra's guarantees the shortest path, but only because it searches every single node at each depth before looking further. There are many graphs which cannot be practically searched this way in a reasonable amount of time. A* can handle some of these graphs in a reasonable amount of time, but in order to do so it may have to sacrifice the ability to always find the shortest path (A* can still find the shortest path if given a proper heuristic, but it was clearly not given a good heuristic here). Ultimately, there are many cases when we need an algorithm that can simply find any path at all rather than the shortest one, specifically. In this sense, A* is definitely still a pathfinding algorithm, even if it doesn't necessarily find the best path.
@@homeworkhopper4610 yeah, especially for a weighted graph then I don't believe there is any proper heuristic that wouldn't require costly pre-processing of the graph.
For game AI, A* is super useful because I just need a "pretty good" path calculated very fast.
@@homeworkhopper4610 Uh no that's now how A* works. You are describing algorithm A not A*. A* is used to describe algorithm A with a admissible heuristic: one that will produce a optimal path every time. Aka heuristic
Looking at the video description, you can implement A* with greedy-best-first search since those are two different algorithms. So this is more of a Djikstra va Greedy-best-first search.
Can you make a tutorial of how make this?, this is incredible
Beautifully animated
Dijkstra is like doing work meticulously. A* is like doing "ehh, whatever, close enough."
That's not true; A* also finds the best solution. It just has extra information to prevent it from walking in the wrong direction.
As a sidenote: The algorithm shown in the video is not an A*, it seems to be a greedy heuristic path finding algorithm. A* is guaranteed to return the same result as Djikstra. Djikstra can actually be expressed as an A* with the "walk in the right direction" heuristic set to zero.
This is not the fastest route on either one, this is a simulation of a path of least resistance (A*) and the other is a simulation of first discovery (Dijkstra)
both can connect the dots, neither are exactly accurate.
A* is unable to represent the speed of an object since Evey line has its own speed. Every intersection is a dilemma, and the less decisions it has to make the faster it moves.
Dijkstra is unable to connect obvious paths if the map appears broken until a path that connects the two is discovered. It then automatically assumes that this is the fastest path (first discovery) as seen in the last example. Even if there is a more efficient path.
That poorly-implemented A* reminds me of that ancient Intel joke:
me: what's 27/14
pentium: 3
me: that's wrong
pentium: maybe, but fast!
superb animation i got an idea for a new video game
I think you used a bad heuristic for A* . I was yelling “Manhattan Distance” at my screen, i bet that would work really well in NY example. Edit: Remembering A*, the heuristic works best if it (almost) always better than the real path. So euclidian distance at 60mph should work. Curious what you used?
This isn’t A*. Look at the description
Wonderful!! Just wow ✨✨✨
Is it possible to merge the intentions of both algorithms to find a partially efficient path while also ensuring there’s a lesser time for the algorithm to calculate?
I read through like 5 comments and I figured out they were people with an intellectual level 10 times higher that my standard 9th grade A scoring self right when I saw heuristic checking as a term
In a way, yes. What they claim is "A*" is not really A* it's Greedy-Best-First Search.
When make a path, Dijkstra makes decisions based on distance from start to the next step, while Greedy-Best-First Search makes decisions based on distance it (inaccuraty) guesses (that's the heuristic) there is between the next step.
A true A* combines both aproaches and makes decision based on the sum of both.
why does it flash bang me when it finds the path?
So it comes down to: "Are you more in a rush of finding a path or to actually go there?"
A* is optimized dijkstra. If yout set the weight of the cost funtion to zero in A*, you basically only the path information(Dijkstra).
finnally I found it, thanks
would be cool to see how you made the visualisations
Is there any documentation or resource to learn how to create this node map to run a simulation based on our algorithm?
Would be really helpful for us too : )
A* is so much faster that it can afford to find a number of more paths so it can then evaluate the shortest of those.. and still likely finish processing faster than Dijkstra.. so it would be faster and very likely to provide the shortest route every time..
Love the visualization
can you make a tutorial how you do that, especially with blender python api
Very cool!
Astounding!
could you give out tutorial?
This is wild but the location you chose on the new york map is my house
Visually, in Rome, Djikstra's path seems like a better one (although it takes 21s to find).
is it faster to climb straight over a mountain or go around it?
the length of the path may be longer, but the amount of time it takes to traverse is shorter
i submit that the a* implementation found the shortest *temporal* route
the expressways and bypasses it picked _should_ be faster timewise due to their higher speed limits and lower number of traffic lights
Does A* have to flashbang us?
Why don't the source and target actually line up with the map
Fun fact. A* breaks apart when you have more then 1 target.
Because it turns into O(X) while the other one stays at O(1) no matter how many targets are left.
Fun fact. A* does not break with multiple goals if you know what you are doing. Just search in reverse. Make the original start the goal and all the original goals as open nodes and it trivially finds the closest goal in a single search. It also works just fine with multiple goals if you just make the heuristic be the euclidian distance to the nearest goal. It will take longer than the reverse search but it will still give you the shortest path with only a single search. The only thing that breaks A* is wormholes(nodes with a cost of zero in between them). For all other problems you might encounter while using A* there is a simple solution if you know what you are doing.
@@arikontinen7688 It breaks apart because the computational cost becomes just that much worse, while Dijkstra's algorithm stays the same.
Ofc you can try to optimize the way you aproach it, but A* stays always in the multiplier cost and sadly that's not avoidable :)
Also you can optimize Dijkstra's algorithm to be a lot quicker.
If your target is rather close and you know the distance you can simply stop nodes from scanning if their total travel distance exceeded the furthest target distance reached.
And you can keep track if all targets were found :)
@@Speiger Yeah sorry to tell you this but you are just wrong. A* will always be the same or fewer operations than dijkstra no matter what you are doing. Does not matter if you have multiple targets or not. If you only need to find the best path to any one of the targets A* will be better. If you need a path that visits all the targets then use A* to find distances between each pair and after that solve for the traveling salesman problem. If you try to use dijkstra to find a path that visits all targets directly without first working out the distance between pairs etc it will scale O(X^X) and you will regret your decision to even attempt doing it that way. And if you are not trying to solve the traveling salesman problem you should never need to find a path to all the targets. Just the closest one. If your implementations show a different result then you implemented A* wrong or your graph is too small that the difference gets lost in the noise. Also dijkstra is not O(1). Both dijkstra and A* scale with the size of the graph. A* however scales a lot better.
If someone claims there is a situation where dijkstra scales better than A* they do not know what they are talking about.
@@arikontinen7688 You misunderstood the problem.
Lets take for example Oxygen not included (ONI)
Which is a game where a dupe (character) can walk to a resource and pick it up.
The problem is that there can be hundreds or thousands of resource objects laying around.
When you use A* to calculate paths you either have to do each one one by one, which technically you could multithread.
Or you could use dijkstra to simply scan the entire map and have paths to every single one in 1 rush.
The traveling merchants problem has nothing to do with dijkstra's strengths, its an entirely different problem because it assumes 1 starting point and you want to visit all targets in the fastest order, while dijkstra's strength is: I want to find X and i have 500 possible connections, which one is the closest or which are the paths to all of them.
Edit: Knowing all paths can be also useful because you can simply cache them and update them as you walk so you don't have to path again.
A* will simply break by the amount of overhead due to duplicated work since it can't really keep existing work and unless all paths have 0 overlap you are a lot faster with dijkstra then with A*
To go back to ONI, you will have a ton of duplicated pathing which means dijkstra's algorithm will simply outperform A* by miles.
If you can't see that in this scenario which is really common in building games then i am sorry you have no idea you are talking about.
Now to make concessions:
dijkstra isn't the perfect algorithm that beats everything.
It is really good if you have a ton of targets or don't know where your targets are like you can not calculate a "distance" at all.
But the moment either of these are not a factor it breaks apart and is really slow.
A* on the other hand is really good if you have information about distance and you have single targets. Which a TON of cases have. Then A* is really hard to beat.
But A* isn't as perfect as people make it out to be.
Know the cons and strengths of your algorithms.
@@Speiger No. You misunderstood the solution. A* does not need to do any duplicated work. In your ONI example with A* you would put all the resources as open nodes(starting postitions) and the dupe as the goal. Initiate the search and it will find the closest resource to the dupe faster than dijkstra with a single search no duplicate work needed. Or if you want to search from the dupe to the resources, your heuristics is the distance to the resource closest to the node but that is the slower approach as your heuristic function becomes quite slow. You do not do them one by one. You add them all at the same time and the algorithm searches from the best candidates first. If you actually understood how these algorithms work you would have known that. Dijkstra is just A* with a heuristic of 0. Which means that no matter what as long as the heuristic is admissible(the guessed distance to the goal is always smaller or equal to the real distance) then at the worst case scenario A* matches dijkstra and on average it always beats it. It only breaks if the graph contains nodes with a cost of 0 or lower between them because that forces the guess to always be zero which effectively forces it to perform the same as dijkstra. This is a fact and no matter how you try to define the problem it will not change.
If your heuristic is admissible A* will never search a node that dijkstra does not search. If the heuristic is admissible then there is no problem where A* would search more nodes than dijkstra. It is simply impossible. Any time you think you have found a case where dijkstra is better than A* you have just implemented A* wrong.
Turns out one cannot simply use the Manhattan distance in Manhattan.
Ok so A* finds a path fastest and Dijkstra finds the fastest path? The comparison seems a little weird.
Why is the comparison weird? They're both pathfinding algorithms. They simply serve different purposes.
Oh i thought this was a speed comparison. My bad.
A* in this case was implemented incorrectly. It always finds the shortest path if implemented correctly.
Ok, so it should find the shortest path? I don’t really know much about this, but I’m very interested. I once implemented Djikstra as a path finding algorithm in a simple game. That’s why I was surprised to find something so much faster. But then I saw that It took a much longer route.
@@redbeardrichardYes, A* should also find the shortest path if implemented correctly.
Hello, Please can someone tell me how to do this, is there any github repo on this project, please let me know if anyone has resources on this ?
Para saber realmente cual es mejor seria probandolo en la vida real los dos tipos de sistemas, teniendo en cuenta el trafico y las distintas velocidades de las vias ya que muchas veces el mas corto no es el mas rapido
Either that A* is not properly implemented or they're using a Potato as heuristic.
WHY DID YOU FLASHBANG MEEEEEEEEEE
At 2:13 the A* should never have gone to the top left of the map. Something is wrong here.
Imagine an AI enhanced A* algorithm that has been trained on billions of these examples.
Amazing!
Cool, but A* and Dijkstra should return the same shortest path
Why is that?
@@myithspa25because if implemented correctly, both algortihms should return the single shortest path, of which there is only one
@@Zeos-pk3wh Not necessarily only ONE, but only one length yes
Nope, Dijkstra searches all directions evenly whereas A* is weighted by the "as the crow flies" distance to the objective
Dijkstra always find the shortest path, A* compromises that goal to prioritise minimising search time, they behave totally differently
Great visu ! Do you have a Git where we can follow your work ?
I just got flashbanged a few times
Is it possible for Dijkstras algorithm to log all the paths to all the nodes it searched on the journey to its Destination? Then you store these for later retrieval?
your description says you used “greedy best first logic” - that is not A* which is why you don’t get the optimal solution
Great stuff! :)
Thank you so much for commenting! Your video from a few months ago on A* visualization was a huge inspiration to my group! I hope you have an excellent holiday season
Yeah it's pretty cool but this isn't even A*
Coud you do tutorial on how to work with geo data?
Tutorial de como usar blender please!
Excelent Job! Which tools have you used to make this?
Thanks for the compliment! I have added some more details to the video description.
A* is not implemented correctly. Why bother looking for a first arbitrary path solution, we want the shortest.
Oh, so that's why gps in GTA games are always wrong.
They implemented A* incorrectly. A* always finds the shortest path they just made a mistake
What was the heuristic function used in this implementation?
They didnt use A*. They used Greedy-Best-First Search.
Fix the title this is not A* it's just A
You could have shortened this video by probably at least a minute by not pausing so long dude.
... and implementing A* correctly
😮
A* is basically Dijkstra with heuristics. If you don't have the same results it means you did a poor job implementing dijkstra base
after reading their comments they probably fucked up A* instead (and implemented some greedy first algorithm)
Yeah A* without the heuristic IS Dijkstra, which means that the differences in the output are going to be consequences of your heuristic
a star assumes to always know the absolute distance
no, thats a heuristic, not the algorithm itself
@blissful4992 actually that is a part of the algorithm. A heuristic can have a portion of total knowledge, rather than exclusively local vantage. A star is only more efficient because the bird's eye distance of each node to the destination is known, which is a form of optimal selection filtering.
edit: literally called a star because "true north" is calculable
@@0MVR_0 False. Multiple heuristics exist that aren’t purely based on distance. Different distance heuristics exist aswell, like Euclidean and Manhattan.
@@blissful4992 pedantic and irrelevant. a star utilizes absolute meter which is the critical factor for its optimality
Singapore research !
00:33 00:57 [01:43] [[02:14]]
A* is fast, but it’s weakness is obvious: moving backwards as part of the solution
very beautiful project , i want to make my own,please guide me, i am currently learning sorting algos in python
what? you are unable to at least read some english text and tell us what tf is that a* algorithm?
Of course it starts in Rome. All roads lead to Rome.