# 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/… Apr 23, 2013 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. Apr 23, 2013 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). Apr 23, 2013 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... Apr 23, 2013 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. Apr 23, 2013 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? Apr 23, 2013 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 Apr 23, 2013 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 Apr 23, 2013 at 8:45
• @G.Bach: Non-simple paths allow edges to repeat. (I guess it depends on your definition though.) Apr 23, 2013 at 17:08

Non-DP solution so it's less efficient but a bit more general: we will find shortest path using $$k$$ edges from $$v$$ to any other $$u\ne v$$ in $$V$$.

We'll make more copies of the graph so we'll have $$G_0, G_1,..., G_k$$ in total. Each original edge $$e=(u,v)$$ will be connecting $$u\in G_i$$ to $$v \in G_i+_1$$ for all $$0\leq i\leq k-1$$. Denote $$u_i$$ the copy of node $$u$$ in $$G_i$$.

Run Dijkstra algorithm from vertex $$v_o$$ (all non-negative weights) and get $$\delta (v_0,u)$$ the shortest path from $$v_0$$ to each $$u$$ in this "master graph", in particular to each $$u_k \in G_k$$. You can get now your desired shortest path.

Note that each path from $$v_0$$ to some $$u_k$$ contains exactly k edges. Complexity is $$O(k\cdot(|V|+|E|))$$ for constructing the graph. Since there are now $$k|V|$$ vertices and $$k|E|$$ edges Dijkstra's run time is $$O(k\cdot (|E|+|V|log|V|))$$ using Fibonacci heap.