Delay Constrained Shortest Path in $O(D \cdot |E|)$ time I have the following homework exercise:


  We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated
  source node s∈V and target node $t \in V$, where $w\colon E \to Z^+$ and $d\colon E \to Z^+$. The
  values $w_{i,j}$ correspond to arc weights, $d_{i,j}$ correspond to delays,
  i.e., using the arc $(i,j)$ requires $d_{i,j}$ time. We are further given a
  positive number $D \in N$, the delay constraint. Develop an efficient, i.e.,
  $O(D \cdot |E|)$, algorithm to find a shortest path $P$ from some $s$ to $t$, which
  does not exceed the global delay constraint $D$, i.e., $\sum_{(i,j) \in P} d_{i,j}≤D$ (Hint: use a similar approach as the one used in the Bellman
  Ford algorithm).


I was able to find an algorithm that runs in $O(D \cdot |E| \cdot |V|)$ time. However I'm struggling with finding an algorithm that runs in $O(D \cdot |E|)$ time and I'm starting to think, that such algorithm is not even possible to create (although I don't have a formal proof for this).

Could you give me a clue how would such an algorithm look like?
Hint: For $1 \leq d \leq D$, compute inductively the shortest distance between $s$ and any other node at delay at most $d$. Each such iteration runs in $O(|E|)$, so the total running time is $O(D|E|)$. (This assumes that the graph is connected. Otherwise you have to replace $|E|$ with $|E|+|V|$.)