Shortest path with exactly $k$ edges

Question

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.

Answer 1

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.

Answer 2

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.