Consider the following problem:There are $n$ points in the plane.Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way that minimizes the cost of the total path.The weight of each edge changes depending on the path followed.For example imagine $n=3$: $A$, $B$, $C$ and we start at $A$. The weight of the edge $xy$ is $Sd_{xy}$, where $d_{xy}$ is the distance between the points $x$ and $y$ and $S$ is a given constant)If I pick the edge $A\to B$, the weight of the edge $B\to A$ is now$(S-s_B)d_{AB}$ because $B$ changes $S$ by a constant amount $s_B$. Similarly if I pick the edge $A\to C$, the weight of the edge $B\to C$ is now$(S-s_C)d_{AC}$ because visiting $C$ changes $S$ by a constant amount $s_C$. Developing the $n=3$ case, imagine S=11, $d_{AB}=5,d_{AC}=3,d_{BC}=4$ and $s_{A}=2,s_{B}=5,s_{C}=4$.Then there are 4 possible paths:A->B->C->A with cost $11*5+(11-5)*4+(11-5-4)*3$(we stop once we reach A because 11-5-4-2=0)A->B->A->C with cost $11*5+(11-5)*5+(11-4-2)*3$A->C->B->A with cost $11*3+(11-4)*4+(11-4-5)*5$A->C->A->B with cost $11*3+(11-4)*3+(11-4-2)*5$For $n=4$ there will be 3*3!=18 possible paths and so on.I know that $s_A+s_B+s_C=S$. This generalizes for $n$ points. What is an efficient algorithm for finding the minimum cost path?
Fast algorithm for finding a minimum cost path through points in the plane
dynamic programming;greedy algorithms