Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
We have a directed graph $G=(N,A)$ where $N$ are the verticies $N=0,1,2,3,4,5,..,n$ the starting location is node 0. For each arc $a=i-j$ in A we have a distance $d_a>0$ So we want to start and end at 0 in a cycle.
Model the TSP as a shortest path problem. Create a modified directed graph.
I am not sure how to do this. The only thing I can think of is start from 0 find the shortest path which has all the node say to $u$ and then do $u-0$
One approach is to create a node $(S,u)$ for each subset $S\subseteq N$ and last-visited city $u\in N$. The main arcs are from $(S,u)$ to $(S\cup\{v\},v)$, with cost $d_{u,v}$. You also need an arc from each $(N,u)$ to a dummy sink node, with cost $d_{u,0}$. The problem is to find a shortest path from source $(\{0\},0)$ to sink.
