# Shortest path with exactly $k$ edges

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.

• 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/… – Jim Balter Apr 23 '13 at 2:00
• @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. – Aryabhata Apr 23 '13 at 2:49
• @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). – Jim Balter Apr 23 '13 at 3:44
• @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... – Aryabhata Apr 23 '13 at 3:51

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.

• I would appreciate a non-dynamic programming answer. – Algorist Apr 23 '13 at 0:05
• @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? – Aryabhata Apr 23 '13 at 0:05
• @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 – Aryabhata Apr 23 '13 at 0:18
• @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 – G. Bach Apr 23 '13 at 8:45
• @G.Bach: Non-simple paths allow edges to repeat. (I guess it depends on your definition though.) – Aryabhata Apr 23 '13 at 17:08