How to find the shortest path in a dynamic graph?

Question

Algorithms

The task is not the most trivial, but not the most difficult: to find the shortest path between two points in the graph.
The problem is that, depending on the time (the amount passed over the edges), the location of the edges can change.
Those. I need to find a route from point A to point B with transfers, while taking into account that different routes travel at different times (some once a day, some 2-3 times a day, that is, not so often).
Perhaps this can be done with standard algorithms, but I can’t figure out how. Maybe there are at least some ideas in which direction to dig, which algorithms to study even more carefully in order to find a loophole.

Answer 1

IMHO, your model is not quite correct. The edges of the graph themselves do not disappear, their price changes. That is, if we can get from A to B at time T , then the cost of edge BC will be equal to the time from time T to the time of the earliest arrival of the route from B to C , taking into account the departure not earlier than T + transfer time .

Answer 2

If you can stop at points for any amount of time, then Dijkstra's usual algorithm should work.
If not, then the dynamics of f[t, p] - is it possible to be at point p at time t
Maybe there are better options, but this is the first thing that came to mind

Answer 3

For whatever - you can not in this and the problem.
"dynamics f[t, p]", and where you can read about it, even I did not find any information about this, how to build dynamics into the algorithm or how easy it is to use.
Or is it implied directly the calculation and determination of the value of this function for each waypoint?

Answer 4

Statement: Consider some vertex v. Let's say the earliest moment at which you can get into it is t. If this vertex is on the shortest path from vertex a to vertex b, then there is necessarily a path no longer than that in which vertex v is visited just at time t.
Such a path can be obtained constructively - the beginning is taken from the shortest path to v, and the end from the shortest path from a to b, you may have to wait some time at the vertex before continuing the path.
Given this statement, it becomes clear that you can solve your problem with the standard Dijkstra algorithm to find the fastest path to all vertices. There, during relaxation (recalculation of the minimum distance), you just need to take into account which edge closest to the current rope will become available for passage.

Answer 5

As far as I understand, with dynamic weights, it is necessary to sort out all possible paths in ascending order of edges, calculating the weight of each edge taking into account time, because, as a more always low-edge path, it can turn out to be longer in time. You can build a graph by taking the minimum theoretical time between stops (at the fastest bus) as a weight, and then filter out obviously long routes. For example, a route was found with 5 stops at 3 o'clock, which actually (with waiting, transfers, etc.) will take 5 hours, so we are looking further until the theoretical time of the graph does not exceed 5 hours.