Walk Less – Take the Shortest Path!
When you have to go from the Johnson Museum of Art to Collegetown Bagels, which way do you take? Do you go via the Arts Quad, via West Campus or via Statler Hotel? You’d instantly think “The Arts Quad, of course!”. The answer seems obvious, but it many cases, that’s not the case. When you look up directions between two locations on Google maps or use an equivalent mapping software, there are a number of routes you can take. The way Google maps decides which route is best for you is by using a more advanced version of Dijkstra’s Algorithm, spoken about in more detail at http://motherboard.vice.com/read/the-simple-elegant-algorithm-that-makes-google-maps-possible .
The basic version of Dijkstra’s algorithm is actually quite simple. There is a certain number of locations between the one you are at and the one you go to (represented as nodes) and route between each of these locations (represented by edges). Given different lengths, amounts of traffic and other variables, each of these edges have different weights. A graphical network can be made out of these nodes and edges to observe all our options. Further, this network can be tabulated and Dijkstra’s algorithm can be applied to it to find the optimal route.
The algorithm sometimes seems repetitive, as every time we make a new iteration, we have to update all our previously saved iterations and shortest paths. This might seem very lengthy when done by hand, especially if many nodes are involved, but the sophisticated technology in today’s world can actually deal with hundreds of nodes quickly enough to find the optimal solution in seconds. This is useful because when you think about it in a broader sense, Dijkstra’s algorithm can be used for many more purposes than just mapping out a route between two locations that you want to travel to; it can be used to model any situation where something has to virtually travel between two nodes. For example, the weights could represent the time taken for to go across an edge and not just the distance if that’s the constraint that is relevant to us. In my opinion, Dijkstra’s algorithm currently has the optimal combination of simplicity and efficiency within all the shortest path algorithms out in the world today.