Directed weighted multigraph with dynamic edges - shortest path

Question

I need to create an implementation of a directed weighted multigraph with dynamic edges:

The edges will be changing during the pathfinding, in the following way:

Summary of the pathfinding:

1. Pathfinding starts at S.
2. S -> V1 (through edge with weight 3)
3. V1 -> V2 (through edge with weight 7, as edge with weight 3 is not available for this path).
4. V2 -> V4 is not possible, so we go back for another iteration.
5. S -> V1 (through edge with weight 3)
6. V1 -> V3 (through edge with weight 8)
7. V3 -> V4 (through edge with weight 3)
8. V4 -> E (through edge with weight 6)

Of course, this is a simplification of the process, but to provide a general idea of how the edges would change, according to current path - let us take for example, that if S -> V1 was made via the edge with weight 5, then V1 -> V2 will be possible via both paths. As a conclusion, the available edges for each next vertex in the pathfinding depend on characteristics of the last edge that has been selected.

A real world example that represents this problem could be the following:

We want to use public transportation to reach from the City of Turin (Italy), to the City of Palermo (Italy).

There are several paths with several available transportation services between them. Let us take a look at the path Turin (Italy) -> Naples (Italy) -> Palermo (Italy).

The following trains are available for the path Turin -> Naples:

• Turin -> Naples (departs at 13:00 and arrives at 19:00)
• Turin -> Naples (departs at 15:00 and arrives at 21:00)

Also, the following boats are available for the path Naples -> Palermo:

• Naples -> Palermo (departs at 18:00 and arrives at 01:00 on the next day)
• Naples -> Palermo (departs at 20:00 and arrives at 04:00 on the next day)

So, despite we have multiple edges between the vertices Turin -> Naples and Naples -> Palermo, we only have one available travel option, and it is Turin -> Naples (departs at 13:00) + Naples -> Palermo (departs at 20:00).

My questions are:

1. Is the best way to represent this problem as a directed weighted multigraph (what I have chosen as of this point) - vertices being the cities, edges being the transportation options, weight being the time of transportation (time of arrival - time of departure)?
2. What would be the most efficient way of finding the shortest path of such a graph with dynamically changing edges (no new edges will be added to the graph during traversal, only the existing ones will be turned ON & OFF, depending on the path chosen prior them)?

Answer 1

You can model the problem you have by creating, for each location, a set of vertices, each saying "arrive at X in time Y", for all Ys which are a departing time of a transportation from X.

Then, for each possible transportation service, you'd add a path from its departing time at its departing place to the departing time of the first transportation which leaves after its arrival time at the arrival location, and set its weight to the time difference between them.

Additionally, you need to add edges between different times in the same place, for the action of waiting in place.

For the example instance, you would get the graph

(This assumes the trains are daily, if they aren't you need to remove the edges which aren't valid actions)

After you create this graph (which would have $O(M)$ vertices and edges), you can run Dijkstra's algorithm on it to find a shortest path in time $O(M \log(M))$