If you're trying to find the shortest path on a map, there are better alternatives to Dijkstra's algorithm (DA). One of them is A* search, a heuristic based extension to DA and I made this visualization to compare their performance.
Let's say you're planning a road trip from Bangalore to Delhi and want to find the shortest route between these two cities. Intuitively, you know that you need to head North to get there. But DA is not guided by any sense of direction and nodes are greedily explored in order of their distance from the source node.
As you can see from the visualization, this is like a wavefront spreading equally in all directions. The edges are colored in the order they were visited. A consequence of this approach is that even edges which take us in the wrong direction are explored - you can see that all of the roads in South India are explored.
Can this redundancy be reduced or eliminated? In some cases, yes. For instance, if we knew the exact distance from each node to the destination, we could prioritize nodes which take us closer to the target. But this is as hard as solving the original problem.
A* search circumvents this by using a heuristic - an approximation of the distance from any node to the target node. Through this approximation, exploration of edges is largely in the direction of the target node - the visualization shows a more focused search pattern resulting in fewer edges explored vs DA.
In this case, the heuristic is the straight line distance which is easy to compute if you have the x,y coordinates of each node. Can any approximation be used for A* search? No, it needs to be consistent. One way of creating heuristics is to relax constraints - knock down walls, fly over obstacles (see comments for more information).
Have you come across A* search in an algorithms class? Would love to know if you've used it for any coursework or projects! If you think someone in your network might like this visualization, please share it with them!
Map of roads obtained from - https://lnkd.in/gjaVnejS
#algorithms #cp #dsa #artificialntelligence