# Retrieving the cheapest path of a graph with time-dependent edge weights

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).

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

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'$$.