How to find the shortest path in a graph with waypoints?

Question

Counts

For example, I have a graph with 5 points, which are all interconnected. I need to find the shortest path that will bypass each point once. The end point doesn't matter.

Answer 1

The simplest combinatorial algorithms.
For example, breadth-first search, start a list of runners, everyone takes one step regardless of each other, remembering those vertices and the order they were in so as not to step on them twice and remembering the length of the path traveled.
At each next vertex, the slider is divided into several (for example, by copying) by the number of edges outgoing from the vertex to the vertices visited by the current slider.
If there are no paths, the slider is removed.
After all the vertices have been traversed, we look for among the remaining runners the one with the smallest length of the traversed path and extract the saved path from it.
ps You can cleverly implement path storage in the slider to optimize the cost of n * logarithm of the size of the maze, instead of the square.

Answer 2

You have a traveling salesman problem with a slight change - you need not a cycle, but a path starting at a given vertex and your graph is complete.
There is no simple and quick solution to the problem. There is a complete enumeration: iterate over all permutations (from n-1 vertices) and count the length of the path in that order. The enumeration works very slowly (O(n*n!)) and is inapplicable for large n. If you have, say, 20 vertices, you will not wait for an answer. For 5, as in the example, it will work instantly.
You can use some kind of annealing method or a genetic algorithm, but you may not find the optimal solution if you are not lucky. If not the most optimal solution is suitable, but just a good one, then it’s easier: Generate random permutations and greedily change the order of vertices locally if it reduces the answer (swap 2 vertices, or reverse a piece of the path). You can also do some naive greed: Each time next, take the closest of the vertices that have not yet been bypassed. I repeat that this will not be the optimal solution, but only some kind of approximation.