As a society we are accustomed to the fact that we have a map of the world on our electronic devices and can find the fastest distance to any known place on Earth. We often take this for granted and don't think about the extensive amount of time spent forming the algorithms that make the resource work the way it does. Edsger W. Dijkstra, the man who essentially developed the ‘skeleton’ code for the program, used a ‘shortest path’ problem which, as you can likely tell from its name, finds the shortest path between two points on a graph. This is helpful as we usually to try to find the shortest route between two places, with the graph being the grid like system most streets are allocated into. ‘Shortest path’ problems tend to get very complicated very quickly as there are many different combinations that can grow exponentially. Dijkstra came up with a simplified version that is explained in the gif below.
The gif shows that a computing device first looks at all optional routes from the starting point “1” and takes the shortest route from there. It continues to reassess the shortest distance from the next point as it progresses. Although Dijkstra’s algorithm isn't the only one used in modern maps, it was certainly a great starting point and an amazing way of helping evolve maps into the kind we use today.
Another method used to find the shortest distance that combines Dijkstra’s algorithm is ‘A*’. ‘A*’ uses the idea of recording areas that are already evaluated, which are areas that have already been explored by the algorithm, and recording areas immediately adjacent to those evaluated. It then calculates the distance from the starting point and an estimated distance to the goal point.
The 'A*' algorithm in conjunction with Dijkstra’s algorithm are two of the most popular algorithms used by modern digital maps and are undeniably two of some of the most useful algorithms to have been created.
References:
No comments:
Post a Comment