0
$\begingroup$

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:enter image description here

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)?
$\endgroup$

1 Answer 1

1
$\begingroup$

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 Graph version of problem

(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))$

$\endgroup$
3
  • $\begingroup$ Thank you for the response! I have been having a look at this approach, but have one concern regarding duplicates - what will happen in case there are two trains from different companies that both offer Tur13 -> Nap20 at weight 7? It is an edge case, but it is not impossible to happen. Any feedback on this would be highly appreciated! $\endgroup$ Feb 20, 2023 at 13:15
  • $\begingroup$ @discretecoder This isn't relevant if you only care about the shortest path (you can just keep one of the trains), but if you want some other information (number of paths, for example) you can simply duplicate the edge Tur13->Nap20 $\endgroup$ Feb 20, 2023 at 13:22
  • $\begingroup$ Coming back here to say thank you - I have applied something quite similar to the above graph that you have shown. Your recommendation has been of great help and has vastly reduced my research and implementation time! $\endgroup$ Mar 31, 2023 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.