I have the following homework exercise:We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated  source node sV 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?
Delay Constrained Shortest Path in $O(D \cdot |E|)$ time
algorithms;complexity theory;optimization;shortest path
As a hint, a dynamic programming method can be utilized to reach $O (|E| \ . D)$. To elaborate, in this solution, we should consider two items, which can be saved in a two-dimensional array.The first item holds vertex number, and, the second one maintains delay. Pseudo-code:$dp \ [vertex \ i][delay] = min (dp \ [vertex \ j][delay - d_{i,j}] + w_{i,j}\  , \ dp \ [vertex \ i][delay]);$Therefore, the total time complexity is $O(|E| D)$.