1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ What is the input to the algorithm? Are you given a graph of the weights at time $t$? If yes, why not apply Dijkstra to that directly? If no, how can the problem be solved without knowing that? Please edit your post to clarify the problem to be solved. $\endgroup$
    – D.W.
    Commented Jun 4 at 5:08
  • $\begingroup$ @D.W. I mentioned the input, but I added a summary in the question to be more clear $\endgroup$
    – Sgg8
    Commented Jun 4 at 10:04
  • $\begingroup$ You haven't answered my question. Are the graph weights provided or not? Why do I care how the weights changed previously if they are now fixed? Why does the week matter? Do you mean that the weight of the 2nd edge traversed depends on which was the first edge you traversed? If so, that needs to be explained in the question. If so, what is the nature of that dependence? If it can be completely arbitrary, then there is no solution possible, short of enumerating all possible paths. $\endgroup$
    – D.W.
    Commented Jun 4 at 17:22
  • $\begingroup$ @D.W. yes, the weight func is provided. I updated the question, sorry. The week doesn't matter in general, but here it is the given time domain. And the weight function is week-periodic $\endgroup$
    – Sgg8
    Commented Jun 4 at 18:52

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I defined time-dependent weights, not vertexes. I see you suggest an equivalent approach. But I can't see why your algorithm is correct. Why can we just apply Dijkstra despite adding the time constraint and still get the optimal path? $\endgroup$
    – Sgg8
    Commented Jun 4 at 10:09
  • $\begingroup$ if your time dependent weights are consistent (as in waiting 2 minutes doesn't lead to a 4 minute shorter weight) then you will get to each node in the shortest amount possible. Including the final node. $\endgroup$ Commented Jun 4 at 10:12
  • $\begingroup$ What do you meam by consistent? There is no waiting at each vertex, but the weights could change while travelling to the vertex $\endgroup$
    – Sgg8
    Commented Jun 4 at 18:44
  • $\begingroup$ by "consistent" I meant what I meant in the parenthetical, there is no advantage possible to waiting. $\endgroup$ Commented Jun 5 at 5:45
  • $\begingroup$ Why will this algorithm be correct? $\endgroup$
    – Sgg8
    Commented Jun 5 at 9:38
2
$\begingroup$

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.

$\endgroup$
1

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.