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.