jun_pl_56 wrote:
About Dijkstra, I will give it a try, but I'll have to modify it, as i have to take into account the waiting time between two changes, and also limit the number of changes
(because I'm not sure someone would like to change bus 5 times to go from A to B).
What do you mean exactly by pretty fast? For me it is important to do everything within a second (sending the request to server, processing the request, sending the K shortest paths back, and displaying them on the map), with a good internet connexion obviously.
I suspect your 1 second will be swallowed up by the network without leaving anything for the routing.
Since you have now expanded the problem from just a shortest path to the K shortest paths you have a lot more work to do. For one thing, you need to decide whether or not the K shortest paths should be disjoint (containing no common node or link except the starting or ending link).
For this I have only ever used the Suurballe algorithm which finds the pair of disjoint shortest paths. I understand it can be extended to the K shortest disjoint paths but I have never looked at it.
>
About walking you're right, it might be smarter to differentiate it. I'll investigate it later and let you know the results.
The problem is not as simple as it sounds, as it implies dynamics graphs, multi-criteria searchs and some extra issues proper to public transportation.
As I see it, there are at least three parts to the dynamics. First one has the slow moving dynamics caused by the way the timetable changes during the day/week, second one has the statistical dynamics caused by local traffic conditions and finally one has the dynamics associated with person making the journey (how fast he/she walks).
These last two are the real problem areas. Many many years ago (1979) I did some very interesting work on 'covariance analysis' where one estimated the mean and covariance propagation through a non-linear dynamic system. I can see that this work might have an application here but I have not thought it through and it certainly will not be computed from scratch in 1 second. Again, I have not thought it through but I can see that much of the covariance calculation can be done as a background thread that sets up the network for use with a much quicker algorithm such as Djikstra.
This sounds an interest (college?) project.