New answers tagged efficiency
0
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.,...
Top 50 recent answers are included