Skip to main content



A More Efficient Shortest Pathing Algorithm

In my last blog post I briefly discussed the value of finding a shortest path between 2 nodes on a weighted graph, and mentioned Dijkstra’s Algorithm – a way for a computer to algorithmically find such a path. Now, while Dijkstra’s Algorithm is guaranteed to terminate and find the correct answer – assuming that there is a path connecting our 2 nodes, A and B, in the first place, it does run into performance issues as the size of the graph increases. It’s not exactly very efficient – for every node, we’re checking all nodes connected to it that we haven’t checked before, in an order that minimizes tentative distance to A. We don’t actually know anything about B with respect to the current path being examined, other than whether we reached it or not. For example, imagine you’re at a subway station somewhere, and you’re trying to get to another subway station that you know is roughly to the north of you. Say there are 2 stations immediately connected to your current station, one 2 miles to the south, and one 5 miles to the north. Under Dijkstra’s algorithm, we would first take the downtown route first, since it’s closer to our current location (2 vs 5 miles) and completely disregard the fact that we’re going in the opposite direction of where we want to end up. Even this backwards approach, however, will eventually result in the optimal path after enough iterations, but only in a roundabout manner in which the algorithm realizes that going south is not, in fact, the best idea when our goal is to the north.

So how do we devise a more efficient algorithm? Continuing with our subway example, wouldn’t it be beneficial for the algorithm to check the station 5 miles north of us first, since we know our destination is to the north? Most definitely. If we modify Dijkstra’s a bit so that we’ll consider some other, outside heuristic in addition to the minimum tentative path (like what a human would do with the above example), we can greatly shorten the amount of time and computation needed to find the exact same result. This is basically the A* search algorithm: identical to Dijkstra’s except the addition of a heuristic along with the tentative distance in the “choose where to go next” step as a guiding hand. For the subway example, the heuristic could be something like the straight line distance from a station to B. Intuitively, what the algorithm is doing is, for every iteration, trying to minimize the distance from our current location to our destination, while at the same time keeping track of how far we’ve already traveled. This is a contrast to Dijkstra’s, where the distance to the destination isn’t considered at all. In fact, Dijkstra’s Algorithm is a special case of A* where the heuristic value of any node is 0.

A* isn’t without its shortcomings however. First, it requires some sort of estimate of cost to the destination node to form the basis of the heuristic. It’s relatively simple in the above subway example, but depending on what the graph is modeling, there might not be an accurate cost estimation. Second, it is paramount that the heuristic is admissible – that is, it never overestimates the actual cost to get to the destination. Otherwise, A* won’t find the shortest path at all.

http://motherboard.vice.com/read/the-simple-elegant-algorithm-that-makes-google-maps-possible

Comments

Leave a Reply

Blogging Calendar

October 2015
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  

Archives