CODEWITHSUNDEEP
algorithmgraph
Myah
Myah

Reputation: 71

Find the shortest path in a graph visiting all nodes

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.

Upvotes: 6

Views: 18278

Answers (2)

amit
amit

Reputation: 178511

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.

Upvotes: 7

Igor Karbachinsky
Igor Karbachinsky

Reputation: 385

Try to look at Dijkstra's algorithm

The basic idea is to filter the routes that traverse all the nodes and get the route with the shortest path.

Bu actually this may be not an optimal way.

Upvotes: -6

Related Questions