6
$\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$
4
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 3:51

2 Answers 2

13
$\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$
10
  • $\begingroup$ I would appreciate a non-dynamic programming answer. $\endgroup$
    – Algorist
    Apr 23, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 17:08
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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