Suppose we have a graph $G=(V,A)$ with $n$ nodes. For every arrow $(i,j)$ in $A$ we have a length $l(i,j)$. We want to find a path from $n$ back to itself, which travels through every node only once. On top of that, we have an extra condition. We may only travel the nodes in a certain order: first from $n$ to $1$ in descending order. Then from $1$ to $n$ in ascending order. Hence $(542135)$ is allowed, but $(534125)$ is not. I am asked to find the shortest allowed path with dynamic programming. But I have no clue about how or where to start.

  • $\begingroup$ What's the order of nodes and edges? There is a naîve approach using bitmask but what complexity are you looking for? $\endgroup$ – Phicar Mar 30 '17 at 16:52
  • $\begingroup$ This is all information. I am looking for a recursive relation in terms of $f(i,j)$ or similar. Here $f$ gives the optimal value from $i$ to $1$ back to $j$. From this I suppose I can find $f(n,n)$. $\endgroup$ – AsMek Mar 30 '17 at 20:10

Along the lines of the idea you had for an $f(i,j)$ recursion:

Let $f(i,j)$ be the optimal value of a path from $i$ to $1$ to $j$ that uses all the nodes $\{1, 2, \dots, \min\{i,j\}-1\}$. (If we want to know the actual path, we can as usual store the optimal path when we compute $f(i,j)$.)

Then the value $k = \min\{i,j\}-1$ can only occur at the beginning or the end of this path, so we have $$f(i,j) = \min\{ l(i,k) + f(k,j), f(i,k) + l(k,j)\}.$$ As a special case, we have $f(i,1) = l(i,1)$ and $f(1,j) = l(1,j)$.


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.