Find the shortest path in a graph visiting all nodes

Question

I have a weighted and undirected graph G with n vertices. Two of these vertices are X and Y.
I need to find the shortest path that starts at X, ends at Y and passes through all the vertices of G (in any order).
How I can do this?

This is not the Travelling Salesman Problemm: I don't need to visit each vertex just once and I don't want to return to the first vertex.

Answer 1

This problem is basically NP-Hard, I am going to give a sketch of a proof (and not a proper reduction), that explains that unless P = NP, there is no polynomial solution to this problem.

Assume torwards contradiction that this problem can be solved in polynomial time O(P(n)) by some algorithm A(G,x,y)

Define the following algorithm:

HamiltonianPath(G):
  for each pair (x,y):
      if A(G(x,y) == |V| - 1):
          return true
  return false

This algorithm solves Hamiltonian Path Problem.

-> If there is a path between some pair x,y that goes through all nodes and its length is exactly |V|, it means it did not use any vertex twice, and the path found is Hamiltonian.

<- If there is a Hamiltonian Path v1->v2->...->vn, then when invoking A(G,v1,vn), you will find the shortest possible path, which its length is at most |V|-1 (and it cannot be less because it needs to go through all vertices), and the algorithm will yield true.

Complexity:

Complexity of the algorithm is O(n^2 * P(n)), which is polynomial time.

So, assuming such an algorithm exists, Hamiltonian Path can be solved in polynomial time, and since it (Hamiltonian Path Problem) is NP-Complete, P=NP.