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

• Looks like it was some kind of whitespace or nonprinting character, then, since there's nothing before the summation sign in your image link. I edited and deleted the mystery character. – David Richerby Oct 19 '15 at 17:40

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

• Note the OP only wanted a hint since this is a homework question. – Yuval Filmus Oct 19 '15 at 18:40

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

• In your solution, each iteration runs with $O(E \ log E)$ by the means of Dijkstra algorithm; therefore, the total time complexity would be $O (D \dot E \ log E)$ – beginner1010 Oct 19 '15 at 18:01
• I don't think so. You don't have to use Dijkstra's algorithm. You go over all edges, and for each edge $e$ you ask yourself: what if $e$ was the last edge in a path from $s$ to somewhere? This only takes constant time per edge. – Yuval Filmus Oct 19 '15 at 18:07
• That's very similar to how my algorithm works. But how can I make one iteration run in $O(|E|)$? I'm using Bellman Ford so I'm calling Relax method in a 3 nested loops over all vertices, delays and edges, therefore $O(D \cdot |E| \cdot |V|)$. – dash Oct 19 '15 at 18:09
• Don't use Bellman Ford and don't use three nested loops. You're only asking for a hint so I won't give away the complete solution. – Yuval Filmus Oct 19 '15 at 18:10
• Have you considered that the shortest path means a path $p$ that $\sum w_{i,j}$ is minimum where $i,j$ are consecutive vertices in path $p$? – beginner1010 Oct 19 '15 at 18:18