OK, but how does it figure the shortest route?
A The applet reads a small data file from the web site that contains information about every subway station, and about the links between each station. Each link contains additional information about which line connects the two stations, what time the two stations are connected using this line, and a weight. The weight is used to account for longer runs between stations, such as those that cross under the East River. Special links are included in the data to represent transfers between stations. The CGI program that runs the Google Maps version is the same, except that the data file lives on the web server, and the CGI program reads it from there. When you select two subway stations, the applet uses a “priority-first search” algorithm. Starting at the first station, it builds a potential subway route to each station that has a link to that station. It puts that route in a “priority queue”. Once it’s done that for the current station, it removes the link with the smallest total weight fr
