2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ $w$ maps to some positive real number, but is not always increasing. $\endgroup$
    – Alex
    Dec 28 '21 at 20:10
  • $\begingroup$ In that case, the longest length path could be the path with minimum cost? $\endgroup$ Dec 28 '21 at 20:13
  • $\begingroup$ arxiv.org/abs/1909.06437 $\endgroup$
    – Pål GD
    Dec 28 '21 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
    Dec 28 '21 at 20:15
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.