Simple Path to Route Algorithm

Question

I'm currently conducting research into subway paths, but stand in front of a problem, with no programming knowledge and an extremely short time-limit. Probably the question I am asking is trivial, but I would be very happy if you could point me in the right direction or to the right forum!

Having generated all possible routes a passenger can take underground for a specific city subway system with a starting, transfer and exit station, I now have to find the on-vehicle travel time for each route. I have excel-style data for each single link of the route, but these have to be ordered and added up for each vector of (starting, transfer, exit) to give me the total travel time.

Take for example the following route: A -> B -> C and I have information on the traveltime for each line, e.g. A4 -> A5, A5 -> A6, A6 -> A, A -> ... -> B and B3 -> B4, B4 -> B5, B5 -> B6, B6 -> ... -> C, where each k = {An, Bm, C} is a station and A is the starting point, B the transfer point and C the exit point for the route.

How can I write a program, which goes through the excel observations and adds up all the relevant travel time for each of the routes?

With about 50000 routes considered, this can be hugely time-intensive to be done manually. Any help on this would be greatly appreciated! If anything is unclear, I will be glad to try and clarify what I mean.

Best

Answer 1

A practical complication of such travel time estimates is the time spent transferring from one line/train to another.

If all you aim for is the minimum travel time, then there are simple relatively fast algorithms to find one or all of the "optimal" routes. See Dijkstra's shortest path algorithm for a single start and destination, or Floyd-Warshall algorithm for all pairs of starts and destinations.

From the mention of "no programming knowledge" and "excel observations" it sounds as if you'd prefer some sort of spreadsheet implementation. I don't think that is going to prove satisfactory, but perhaps you could find some supporting resources to help you out.