There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient algorithm to find the path of graph with the lowest cost, where weights of edges depend on what time the edge is being walked through. I need to take into account how the situation changes during the path traversal after each passed edge. How can I do this? Maybe there are ways to at least try to optimize the cost to be as low as possible?

Somewhat formal definition:

Given a graph $G=(V,E)$, time-based edge cost function $w_{v_i,v_j}(t)$ and a constant time to walk through an edge $t_{v_{i},v_{j}}$, find path from starting point $v_s$ to finish point $v_f$, $P=(v_1, v_2, ..., v_n)$, where $v_1 = v_s$, $v_n = v_f$, such that $\sum_{i=1}^{n-1}w_{v_{i},v_{i+1}}(T_{P}(i)) = min$, where $T_{P}(n) = \sum_{i=1}^{n-1} t_{v_{i}, v_{i+1}}$ (time passed since the start of the path)

Basically, the graph is a collection of pedestrian roads of a city area and the cost function is a factor that a pedestrian might want to avoid at the cost of a possibly longer path, such as sun illumination (wants to walk in the shadow) or noisiness/crowdedness (wants to avoid public places).

  • $\begingroup$ $w$ maps to some positive real number, but is not always increasing. $\endgroup$
    – Alex
    Commented Dec 28, 2021 at 20:10
  • $\begingroup$ In that case, the longest length path could be the path with minimum cost? $\endgroup$ Commented Dec 28, 2021 at 20:13
  • $\begingroup$ arxiv.org/abs/1909.06437 $\endgroup$
    – Pål GD
    Commented Dec 28, 2021 at 20:14
  • $\begingroup$ Yes, this may be the case. I need to minimize the total cost, even if it results in a longer path. $\endgroup$
    – Alex
    Commented Dec 28, 2021 at 20:15

1 Answer 1


This is solvable using a product construction. You construct a new graph $G'=(V',E')$ where each vertex in $V'$ has the form $\langle v,t \rangle$, to keep track of both which vertex you're at ($v$) and the current time ($t$). Then, find a shortest path in $G'$.

To learn more about this approach, for some other examples of a product construction, see, e.g., Shortest path given correct order of colours?, https://stackoverflow.com/q/5370902/781723, Restricted traversal on an undirected graph, Dijkstra's algorithm to compute shortest paths using k edges?, How hard is finding the shortest path in a graph matching a given regular language?.

  • $\begingroup$ That seems wildly impractical. Time is a continuous variable—the size of the graph this approach produces will depend entirely on how granular you subdivide the time. $\endgroup$ Commented Sep 3, 2023 at 7:29

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.