# Motivation

The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two places.

We all know the classical "Shortest path problem": Given a directed graph $G=(V,E)$ with edge-lengths $w_e\in\mathbb{R}_0^+,\,e\in E$ and two vertices $s,t\in V$, find the the shortest path between $s$ and $t$ (i.e., the path minimizing the total edge-length). Assuming non-negative edge-lengths, there are various algorithms and the problem is easy.

This is a good model for the case that we are walking, for example. The vertices are crossroads in our network of roads and each edge has fixed length -- in meters, for instance. Another possible interpretation of the edge-weights $w_e$ is the time that it takes us to go from one of its vertices to the other. This is the interpretation that interests me now.

# Problem

I now want to model the following situation. I want to travel from point A to point B in a city via public transport and minimize time. The public transport network can be easily modelled as a directed graph as you would expect. The interesting part are the edge-weights (that model time) -- public transport (buses, for instance) leave only in certain intervals, which are different for every stop (vertex in graph). In other words -- the edge-weights are not constant, they change depending on the time we want to use the edge.

How to model this situation: We have a directed graph $G=(V,E)$ and an edge-weight function $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$ that takes time as its argument and returns time that it takes to use the edge in our path. For example, if the bus from vertex $v$ to vertex $u$ leaves at $t=10$ and it takes $5$ time and we arrive at vertex $v$ at $t=8$, then $w(vu,8)=7$ is the edge-weight. Clearly, $w(vu,10)=5$.

It is slightly tricky to define total weight of path, but we can do it recursively. Let $P=v_1v_2\ldots v_{k-1} v_k$ be a directed path. If $k=1$ then $w(P)=0$. Otherwise, $w(P)=w(P')+w(v_{k-1}v_k,w(P'))$, where $P'$ is the sub-path of $P$ without $v_k$. This is a natural definition corresponding to the real-world situation.

We can now study the problem under various assumptions on the function $w$. The natural assumption is $$w(e,t)\leq w(e,t+\Delta)+\Delta \text{ for all }e\in E,\Delta\geq 0,$$ which models "waiting for $\Delta$ time".

If the function "behaves nicely" it may be possible to reduce this problem to the classical Shortest path problem. But we could ask what happens when the weight-functions get wild. And what if we drop the assumption on waiting?

# Questions

My questions are the following.

• Has this problem been asked before? It seems kind of natural.
• Is there any research on it? It seems to me that there are various subproblems to be asked and studied -- mainly regarding the properties of the weight-function.
• Can we reduce this problem (possibly under some assumptions) to the classical shortest path problem?
• Here's a natural baseline approach against which more research-level answers can be compared. Model it as a reachability problem by discretizing the time units into a collection of instants $T$, and make a new graph with vertices $V' = T \times V$. You can then put edges $(t_0,v_0) \to (t_1,v_1)$ where $t_1 = w((v_0,v_1),t_0)$. This is already efficient for a lot of use-cases (eg with bus schedules, you just let $T$ be the times when the buses arrive/leave their stops), but doesn't work perfectly all the time (consider when $w$ varies continuously over time), and is slow if $T$ is large. – Andrew Morgan Aug 12 '16 at 22:15
• One simple variant of this problem (where edge weights depend linearly on time) is called "parametric shortest path". – Neal Young Aug 13 '16 at 21:11

This is known as the "time-dependent shortest path" problem. Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which proves that when the weight function of each edge is polynomial-size piecewise-linear, then the shortest path between two fixed points changes $n^{\Theta(\log n)}$ times.