I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most optimal way( in the way that the path is the shortest). What algorithm will you suggest me to use?
Thanks much in advance
This problem is NP-complete. If you do find a good algorithm for solving it, please tell me.
Let $G = (V,w)$ be an instance of the Non-returning Travelling Salesman Problem with vertex set $V$, and weight function $w$. We seek the shortest path that travels through every point in $V$ with respect to $w$. If two vertices $(u,v)$ do not have an edge between them, we will represent this by saying $w(u,v) = \infty$.
We will construct an instance of your problem whose solution can be decoded into a solution to the Non-returning Travelling Salesman Problem. Let $S = V$, and $T$ be an arbitrary set, disjoint from $S$, such that $|S| = |T|$. Let $w': S \cup T \rightarrow \mathbb{R} \cup \{\infty\}$ such that
$$ w'(u,v) = \begin{cases} w(u,v) &\mbox{for } u,v \in S\\ 0 &\mbox{otherwise} \end{cases} $$
So in the graph $(S \cup T, w')$, travelling between points in $S$ is just as expensive as before, travelling from anywhere in $S$ to anywhere in $T$ is free, and travelling within $T$ is free. Let $d: S \leftrightarrow T$ be an arbitrary destination function.
Suppose we had a "fast" algorithm to solve your problem with start points $S$, terminals $T$, destination function $d$ and weight function $w'$. This solution would give us the shortest path that passes through all points in $S$, followed by some path through $T$. Taking only the section of the path that travels through $S$, we will now have the shortest Hamiltonian path through $V$ with weight function $w$, which is the solution to the non-returning Travelling Salesman Problem.
The travelling salesman problem reduces in polynomial time to your problem, so your problem is NP-complete, so, assuming P $\neq$ NP, no good algorithm for solving it exists.