I have the following problem:
Given A directed graph $G = (V, E)$, a start vertex $s$ (in $V$), $length(u;v)$ (could be negative) for every edge $(u;v)$ in $E$ and a time $t(u;v)> 0$ that it takes to traverse the edge $(u; v)$, where each $t(u;v)$ is an integer in $[1,M]$. Finally, we are given a time bound $T$. The goal is to find the shortest path from $s$ to every other vertex, among paths that take time at most $T$ to traverse. I have to use dynamic programming to devise an algorithm for this problem running in time polynomial in $n$ and in $M$.
In this case, since some length can be negative, I've thought to use Bellman algorithm or at least an extended version of this algorithm. I am looking for a path p such that it cost is
Min{length(p): time(p) ≤ T }
could anyone help me with the pseudocode?
Hint: consider a “layered network” with nodes $(u,t_u)$ and a directed edge from $(u,t_u)$ to $(v,t_v)$ if $(u,v) \in E$ and $t_v=t_u+t(u;v)$.