Shortest path between two nodes with time-dependent edge weights

Question

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road segments join together. I want to find the shortest path starting at some vertex $V_s$ at time of week $t$.

Here's why I cannot apply Dijkstra or A* directly. A week is divided into time intervals of length $t_0$ each. The data I have is as follows. For each such time interval, I have a graph of the city road map, where the weight of each edge $(V_1, V_2)$ is the time is takes to travel from $V_1$ to $V_2$. So my weights change as I travel from source to destination. This data makes sense, because the roads are more congested at some times of the week compared to the others.

To summarise, the input is the starting vertex $V_s$, a graph $(V, E)$, a weight function $w(e, t)$, that gives the time it takes to travel across the edge $e$ starting at the time $t$ (it will be the starting time + the time it took to get to the start of the edge), and the starting time of week $t_0$. The weights are time-dependent. They depend on the time already travelled before.

How can I compute the shortest path, given the time-dependent weights? I need a proof of correctness, not just an algorithm.

Answer 1

Instead of having the vertices in your navigation graph defined by only the location you can have vertices defined by location and time.

That way the result of $cost((V1, t), V2)$ will depend on time and give you a $(V2, t+cost((V1, t), V2))$ to insert into the open set.

You can still discard already explored vertices based on only the location like usual.

Answer 2

You need to build a bigger graph (a "product graph", in the jargon). Each vertex is identified by a pair $(V,t)$, where $V$ is a location (a point on the map where two road segments join) and $t$ is a time. Therefore, an edge between two vertices is an edge between $(V_1,t_1)$ and $(V_2,t_2)$. The weight on this edge is given by $w((V_1,V_2),t_1)$. Now you can use Dijkstra's algorithm or A* on this bigger graph.

Moreover, you don't need to build the entire bigger graph in advance. Instead, you can create vertices and edges on-the-fly, as needed. This will be particularly helpful when using algorithms like A* or uniform cost search.