找到访问所有节点的图中的最短路径

- >如果某对 x，y 遍历所有节点，其长度正好 | V | ，这意味着它不会使用任何顶点两次，并且找到的路径是哈密​​尔顿算子 - 如果存在Hamiltonian路径v1-> v2 - > ...-> vn，那么当调用 A（G，v1，vn），你会发现最短的路径，它的长度最多为 | V | -1 （并且它不能小于它，因为它需要遍历所有顶点），并且算法会生成真实的。

复杂性： 算法的复杂性是 O（n ^ 2 * P（n）） ，这是多项式时间。因此，假设存在这样的算法，哈密顿路径可以在多项式时间内求解，并且因为它（哈密尔顿路径问题）是 NP-Complete ，P = NP。

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.

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:

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.