1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 19 '15 at 17:40
1
$\begingroup$

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

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

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

$\endgroup$
10
  • $\begingroup$ 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)$ $\endgroup$ – beginner1010 Oct 19 '15 at 18:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 19 '15 at 18:07
  • $\begingroup$ 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|)$. $\endgroup$ – dash Oct 19 '15 at 18:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 19 '15 at 18:10
  • $\begingroup$ 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$? $\endgroup$ – beginner1010 Oct 19 '15 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.