2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ I also know if we have (0,1) in the regular graph we have (0,1) in the modified graph and we have 2 0 nodes and 2 1 nodes. $\endgroup$ Commented Apr 18, 2022 at 18:51

1 Answer 1

6
$\begingroup$

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.

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