# Graph theory: shortest path with dynamic programming

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.

• What's the order of nodes and edges? There is a naîve approach using bitmask but what complexity are you looking for? – Phicar Mar 30 '17 at 16:52
• 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)$. – 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)$.