00:00 Introduction
01:38 Change the lengths!
06:34 What is good potential?
12:31 Implementation
16:20 Bonus

Tom Sláma's video: https://youtu.be/umszOeerdsU

Our Patreon: https://www.patreon.com/Polylog

Some related things:

— One thing I didn't mention is that Dijkstra's algorithm is designed to solve the problem of finding the shortest path from the starting node to all other nodes of the graph. It does this task very well, in nearly linear time, so there is not much to improve here. It is the problem of finding the shortest path between two nodes where A* is usually an improvement over Dijkstra.

— Here is a link to another example of an A* run from Sarajevo to Eastern Italy. You can see how the algorithm quickly reaches the first city, Tirana, but then gets stuck because of the Adriatic Sea. So it searches along the coast until it finds Italy. After that, it confidently runs through Italy until it finds the destination.
https://github.com/polylog-cs/Astar/blob/main/Explore.mp4

— If your heuristic is not consistent but at least admissible, A* will still return the correct answer, although the time complexity may be exponential to the network size.

— IDA* is a popular algorithm that relates to iterative depth-first search, just as A* relates to Dijkstra/Breadth-first search.

– Perhaps the simplest application of the potential reweighting technique is the Johnson algorithm:
https://en.wikipedia.org/wiki/Johnson%27s_algorithm

– See also this blog post from Codeforces that summarizes some applications of potentials in competitive programming.
https://codeforces.com/blog/entry/95823

– The reason why potentials are often so useful is because they are dual to the concept of distances in the sense of the duality of linear programming.

Symptoms:

– Prove that the heuristics from the video are consistent.

– Prove that the maximum of two consistent heuristics is still consistent. (So if you have two incomparable heuristics, you should combine them in this way.)

— Prove that for any heuristic that is consistent, evaluates to zero for the goal state, and is nonnegative otherwise, A* always explores fewer states than Dijkstra. That is, apart from the time spent computing the heuristic, A* is never worse than Dijkstra at the problem of finding the shortest path between two points.

Big thanks go to: Richard Hladik, Matěj Konečný, Martin Mareš, Yannic Maus, Jan Petr, Vojtěch Rozhoň, Hanka Rozhoňová, Tom Sláma

Links in the video:
maps.google.com
https://geojson.io/
https://public.opendatasoft.com/explore/dataset/europe-road/export/?refine.iccBE
https://stackoverflow.com/questions/29470253/astar-explanation-of-name

Credits:
To create this video we used manim, a Python library: https://docs.manim.community/en/stable/
The color palette we use is solarized: https://ethanschoonover.com/solarized/
Music: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782
Music: Thus Spoke Zarathustra by Strauss from Wikimedia Commons
Scroll image: https://www.pxfuel.com/en/desktop-wallpaper-aadkb
Pictures of the cities are from Wikimedia Commons

Please take the opportunity to connect with your friends and family and share this video with them if you find it useful.