<< Home
Dmitri Nosovicki
Demo applications
| Moscow Metro, 2007 | |
|---|---|
|
This program demonstrates optimal path finding algorithm that is used in Google
maps, etc. Though the algorithm is very simple, it is blazingly fast and
requires no pre-computation on the nodes.
Demonstration finds and represents graphically the shortest path between two stations of Moscow Subway. Moscow subway has 12 lines and 199 stations in total, 73 of which offer transitions to other lines, and 23 of those allow transitions between three or more lines. For every destination there exist hundreds of possible routes, several of which look near optimal; therefore it is often not obvious which route is the shortest one. It adds to the problem that transition times and distances between stations vary. Entire program with its user interface and all graphics fits in under 400 lines of code. Generic A* implementation it contains consists of 25 lines of code, which is, ironically, almost two times shorter than pseudocode A* definition on Wikipedia. |