Graph theory: shortest path with dynamic programming

Question

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.

Answer 1

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)$.