This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming.I'm making a journey planner (or a general timetable application) for all the public transport in my country (bus/train/air).The state of the project is at midpoint, now I'm having a bit of a hard time getting the more difficult part of the application done.Currently, I have all the stops, routes and departure/arrival times.When there are direct connections between two points, all is fine, I can get the trips for a chosen day. The hard part is getting a complete journey when there are no direct lines.Say the user wants to travel from city A to city D, but because there are no direct lines between those cities, he needs to pass through city B and city C.How can I get the optimized routes and transfers for this situation?My ideas so far a gravitating towards using a graph, but in that case I need a Time-Dependant Directed Weighted Multigraph, and I really have no idea at the moment how to implement the Time-Dependant part.Getting just the route can be done by using Dijkstra, A* or FloydWarshall algorithms , but because there are departures at different times, I'm not sure how will this be implemented, to get the optimal solution. I need to take into consideration the duration of a segment (A to B, B to C), waiting time for the transfer, maybe the distance too.Just to clarify, I don't need a single result. I want to get a daily list of all departures from city A that can get the user to city D, with transfers if needed.Basically, what I'm trying to get is something like this (taken from Bulgarian Railways, or for that matter, whichever railway site), a list of all departures for a chosen day going from Sofia to Kystendil making transfer in Radomir if needed:If I'm not clear enough, please ask.I know that this is done so many times (almost any train website has the solution), but I don't know by which terms to even search.So, my question is: can someone give me guidance how this type of problem is solved?Or at least by which terms should I search for ideas and how should it be done.Maybe some suggestions for other sites in the StackExchange network.
Route planning in public transport application
algorithms;graphs;dynamic programming;shortest path