4
$\begingroup$

From Skiena's book The Algorithm Design Manual, chapter 6, problem 22:

Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm to find the shortest path from $v$ to $u$ that contains exactly $k$ edges. Note that the path need not be simple, and is permitted to visit vertices and edges multiple times.

This is not homework, its me preparing for an interview. I have no clue how to approach this.

$\endgroup$
  • $\begingroup$ This is a crosspost of stackoverflow.com/questions/16158433/…, which was closed by a moderator. I also voted to close because it's a duplicate of stackoverflow.com/questions/1690347/… $\endgroup$ – Jim Balter Apr 23 '13 at 2:00
  • 1
    $\begingroup$ @JimBalter: 1690347 is asking for a path, while this is asking for a walk. They are quite different. I suspect the former is $NP$-Hard(two directional edges, with weights $1$ and if $k=n$ and you have a Hamiltonian Path problem), but the latter has an easy dynamic programming algorithm. I suggest you undupe those and downvote the top voted answer in 1690347 :-) which is actually an answer to 16158433. $\endgroup$ – Aryabhata Apr 23 '13 at 2:49
  • $\begingroup$ @Aryabhata They both ask for a path through a weighted graph. But I see now that this specifies two vertices, so they're different questions. Anyway, I can't undup anything ... as I said it was closed by a moderator (for crossposting and other bad behavior). $\endgroup$ – Jim Balter Apr 23 '13 at 3:44
  • $\begingroup$ @JimBalter: Oh sorry, I thought you were a moderator there. btw, even if the old one specified two vertices they are different problems. One asks for a path, and the other allows non-simple paths (i.e. walks). And yes, I know they are weighted paths, I was just proving NP-Hardness of the path version. Anyway... $\endgroup$ – Aryabhata Apr 23 '13 at 3:51
11
$\begingroup$

Since you allow non-simple paths(i.e. walks), seems like a dynamic programming algorithm will work.

For each $1 \le m \le k$, and every vertex $u$, we compute $D[m,u]$ where $D[m,u]$ is the weight of the shortest walk of length exactly $m$ starting at $v$ and ending at $u$. We are looking for $D[k,w]$.

This can be computed as

$$D[m+1, u] = \min_{x \in Pred(u)}\{D[m,x] + w[x,u]\}$$

Where $Pred(u)$ (predecessor) is the set of vertices which have an outgoing edge to $u$ and $w[x,u]$ is the weight of edge $x\to u$. You start with $D[1,u] = w(v,u)$ (allowing $\infty$).

You can add auxiliary structures to find the actual walk.

Running time: $O(k |E|)$.

This is because for each number of required edges from 1 to k, we go through the indegree of each vertex and in total, we visit all $|E|$ edges. We visit all $|E|$ for each number of the required edges ($k$) so the final run time is $O(k |E|)$ .

btw, if we wanted only simple paths, then this is probably $NP$-Hard, as we can set $k=n$ and reduce some variant of Hamiltonian Path problem to it.

$\endgroup$
  • $\begingroup$ I would appreciate a non-dynamic programming answer. $\endgroup$ – Algorist Apr 23 '13 at 0:05
  • 4
    $\begingroup$ @Algorist: You should mention that in the question, then. But I am curious. If you are preparing for interviews, why are you discounting dynamic programming? $\endgroup$ – Aryabhata Apr 23 '13 at 0:05
  • 3
    $\begingroup$ @Algorist: Well, if the only algorithm possible uses dynamic programming, what will you do? Maybe now is a good time to learn dynamic programming? May I recommend: cs.berkeley.edu/~vazirani/algorithms/chap6.pdf $\endgroup$ – Aryabhata Apr 23 '13 at 0:18
  • 1
    $\begingroup$ @Aryabhata Cheers, for some reason dynamic programming wasn't covered in my undergrad degree and I need to read up on it - thanks for that link! +1 $\endgroup$ – G. Bach Apr 23 '13 at 8:45
  • 3
    $\begingroup$ @G.Bach: Non-simple paths allow edges to repeat. (I guess it depends on your definition though.) $\endgroup$ – Aryabhata Apr 23 '13 at 17:08

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.