What algorithm should be used to find the shortest path in an undirected graph through all vertices?

Question

Algorithms

Hello!
Tell me what algorithm to use to find the shortest path in an undirected graph through all vertices (i.e., you need to bypass them all), where the starting and ending points can be chosen arbitrarily (i.e., specifically specified by the user). (?)
Thanks!

Answer 1

You are 100% required by the Hamilton Paths algorithm .
I completed it myself not so long ago, I wrote it in PHP.
The calculation occurs when the number of vertices is from 500 to 1000.
In this case, I use the coordinates converted to radians and decomposed in the adjacency matrix.
Well, then this algorithm.

Answer 2

The Hamiltonian path has nothing to do with it - after all, there is no prohibition to pass the same vertex twice? But this is purely a traveling salesman problem. It also belongs to the NP class. The exact solution will be too long, you have to look for approximate ones.

Answer 3

Your description fits the Floyd-Warshall algorithm. They are looking for the shortest paths from all the vertices in the sun. The algorithm has a very high complexity - O(n^3)

Answer 4

The theory says that exact algorithms faster than 2^n are not known, and approximate ones with an error of 229/228 do not exist as long as P != NP.
For exact ones, in practice they write either the branch and bound method, or write the problem in terms of linear programming and try to find an integer solution. By the way, I would try the second one. You need to take some Gurobi-type solver and check it out.
There are simple approximate heuristics. For example, let's sort all the edges of the graph and try to insert them into our path in ascending order of weight. They write that in practice this gives an error of 15-20%.