<p>This is known as the "time-dependent shortest path" problem.  Indeed research has been done for this problem; see for example <a href="http://dl.acm.org/citation.cfm?id=214078&amp;dl=ACM&amp;coll=DL&amp;CFID=817924255&amp;CFTOKEN=81142653">the classical paper</a> by Orda and Rom, and <a href="https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf">this recent SODA paper</a> 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.</p>

<p>Dijkstra's algorithm can indeed be used for this problem, when the waiting policy is imposed, that is, wait at a node if that reduces the final arriving time.  Without the waiting policy the situation is much wilder: the shortest path may not be simple, subpath of a shortest path might not be the shortest between the two endpoints of the subpath, paths traversing through infinite number of edges may have finite arriving time, etc.  See again <a href="http://dl.acm.org/citation.cfm?id=214078&amp;dl=ACM&amp;coll=DL&amp;CFID=817924255&amp;CFTOKEN=81142653">the paper by Orda and Rom</a> for more discussion.</p>

CC BY-SA 3.0
2016-08-15T07:32:23.657Z
2016-08-15T07:32:23.657Z
Hsien-Chih Chang 張顯之
<p>Are you aware of the "shortest nondecreasing paths" problem? It was defined to model situations such as these. Although it's a bit less expressive compared to your formulation, there are fast algs for it.</p>

CC BY-SA 3.0
2016-08-14T16:13:05.837Z
2016-08-14T16:13:05.837Z
Ryan Williams
<p>If you assume that the times are integral (which makes sense in the case of public transit), you can make a time-expanded network, similar to the one suggested by Ford-Fulkerson for <a href="ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-022-2008.pdf" rel="nofollow noreferrer">max-flow over time</a> (or quickest flow) and find the shortest path in this graph instead.</p>

CC BY-SA 3.0
2016-11-07T00:45:21.757Z
2016-11-07T00:45:21.757Z
Helium
<h1>Motivation</h1>

<p>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. </p>

<p>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.</p>

<p>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 <em>time</em> that it takes us to go from one of its vertices to the other. This is the interpretation that interests me now.</p>

<h1>Problem</h1>

<p>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 <em>minimize time</em>. 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.</p>

<p>How to model this situation: We have a directed graph $G=(V,E)$ and an edge-weight <em>function</em> $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$ that takes <em>time</em> as its argument and returns <em>time</em> 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$. </p>

<p>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.</p>

<p>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".</p>

<p>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?</p>

<h1>Questions</h1>

<p>My questions are the following.</p>

<ul>
<li>Has this problem been asked before? It seems kind of natural.</li>
<li>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.</li>
<li>Can we reduce this problem (possibly under some assumptions) to the classical shortest path problem?</li>
</ul>

CC BY-SA 3.0
2016-08-12T22:15:28.693Z
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
CC BY-SA 3.0
2016-08-13T21:11:35.417Z
One simple variant of this problem (where edge weights depend linearly on time) is called "[parametric shortest path](https://scholar.google.com/scholar?q="parametric+shortest+path")".
Neal Young
<graph-algorithms><shortest-path>
Shortest distance problem with length as functions of time
JS_
# Shortest distance problem with length as functions of time

(Asked by: username_0 on 2016-08-12)

# 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?

**Tags:** graph-algorithms, shortest-path
> **Comments:**
> **username_1**: 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.  
> **username_2**: One simple variant of this problem (where edge weights depend linearly on time) is called "[parametric shortest path](https://scholar.google.com/scholar?q="parametric+shortest+path")".  

---

## 3 answers

### Answer by username_3 on 2016-08-15. Score: 8 | Accepted answer

This is known as the "time-dependent shortest path" problem. Indeed research has been done for this problem; see for example [the classical paper](http://dl.acm.org/citation.cfm?id=214078&dl=ACM&coll=DL&CFID=817924255&CFTOKEN=81142653) by Orda and Rom, and [this recent SODA paper](https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf) 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.

Dijkstra's algorithm can indeed be used for this problem, when the waiting policy is imposed, that is, wait at a node if that reduces the final arriving time. Without the waiting policy the situation is much wilder: the shortest path may not be simple, subpath of a shortest path might not be the shortest between the two endpoints of the subpath, paths traversing through infinite number of edges may have finite arriving time, etc. See again [the paper by Orda and Rom](http://dl.acm.org/citation.cfm?id=214078&dl=ACM&coll=DL&CFID=817924255&CFTOKEN=81142653) for more discussion.


---

### Answer by username_4 on 2016-08-14. Score: 3

Are you aware of the "shortest nondecreasing paths" problem? It was defined to model situations such as these. Although it's a bit less expressive compared to your formulation, there are fast algs for it.


---

### Answer by username_5 on 2016-11-07. Score: 1

If you assume that the times are integral (which makes sense in the case of public transit), you can make a time-expanded network, similar to the one suggested by Ford-Fulkerson for [max-flow over time](ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-022-2008.pdf) (or quickest flow) and find the shortest path in this graph instead.


---

