Graph theory - find path from point A to point B in a tram / bus network
I am currently working on a project to find the most optimal path from one address to another using public transports in a town. Different options will be available
to the user : find the fatest way and also the one with the least number of bus / tramway changes.
There are in the town approximately 1500 stops and 60 different lines, and i am looking for a fast algorithm to compute the path from address A to address B.
There are some constraints, like the respect of schedules (it is a dynamic graph) and also the fact that people will sometimes to walk from one stop to another to change bus / tramway.
I am looking for an algorithm to do that. I have several ideas in mind, like :
- using A* algorithm with some heuristics (i don't know if it fits well to the problem, since we can't really use heuristics like Manhattan distance here, as public transports not always go straight from one point to another).
- computing a dijkstra algorithm to blindy find the address A (but i think it would be too long).
Would you have any idea or opinion on how to do it?
Any remarks, links, suggestions are welcome :)
Thank you !