I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges represent the time taken to travel from one station to another.
For any particular vertex, there might be multiple edges going from that vertex to another (as there could be, for example, a scheduled service that departs from A to B hourly each day - meaning 24 journies in a day and 24 edges between the two vertices for this one journey).
In terms of my analysis, I want to be able to find the shortest path from all stations to all other stations. I can then use algorithms such as BetweennessCentrality on the resultant data to find the most "important" vertices. This type of analysis obviously lends itself to using Dijkstra’s algorithm to find the shortest paths.
However, using Dijkstra’s algorithm will mean that real-life constraints are ignored. For example, Dijkstra’s algorithm won’t take into consideration you can’t set off from station A at 10:00, arrive at B at 10:30 and then take a train from B to C at 8:00 (you are not a time traveller!).
Dijkstra's algorithm also won't take into account time spent waiting in a station for a train to arrive in a situation where a passenger would have to change trains.
I have looked into modifying Dijkstra's algorithm to take these factors into account but as these factors change on a case by case basis you are unable to apply them to the network as a whole.
The ConnectionScanAlgorithm does take real-life constraints into account and scans through a network’s nodes and edges with a given start and end node in mind (I believe this is how train ticket websites find a quickest route).
However, since I need the routes from all stations to all other stations, to make use of the ConnectionScanAlgorithm I have to pass through every combination of station pairings (for me, this is some 36 million combinations) which is far too time expensive.
Are there any algorithms out there which are applicable to this problem?
If not, what is the best way to go about forming a solution?
