I am building a bus routes map for Chennai. I use Postgis. In our database we have one table having all the routes along with unique ids given for them. Second table comprises of bus stop names with its latitude and longitudes. The third table joins the first and second table based on their ids. We have track records for the routes.
I want to construct a function for finding the shortest route between 2 stops which don’t have a common route. For eg, Two stops A and B exist which don’t have any common routes. Say there are 3 other stops- C,D,E. I want to find out which route should I take to travel the shortest distance. If I leave from A, should I get off at C and from C take a bus to B, or get off at C take another bus to D and from there another bus to B, or go to E and then take a bus. Basically I want to find the shortest path for two stops without a common route. Since my database is enormous that needs to be considered while choosing an Algorithm cause it shouldn’t slow down the process.
Could someone please suggest a suitable algorithm which doesn’t take much time?