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.

what happens in this case: u->v, v->u. Is it gonna cost us 2*w? I think it should (I'm just trying o make sure), because if it doesn't you just have to find the MST. — farzadshbfn
Yes, this is NP-Hard, the "relaxation" does not make it any easier. If it was possible to find the shortest path between given two pairs that goes through all nodes, it was easy to find if a graph has a Hamiltonian Cycle by checking all pair of nodes X,Y (there are polynomial number of those). — amit

amit amit · Accepted Answer · 2016-04-16T14:00:57

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.

Find the shortest path in a graph visiting all nodes

2 Answers