Какой алгоритм использовать для поиска кратчайшего пути в ненаправленном графе через все вершины?
Гамильтонов путь тут ни при чём - ведь нет запрета проходить одну вершину дважды? Но это в чистом виде задача коммивояжера. Тоже входит в класс NP. Точное решение будет слишком долгим, надо искать приближённые.
Теория говорит, что точных алгоритмов быстрее 2^n не известно, а приближенные с ошибкой 229/228 не существуют, пока P != NP.
Для точных на практике пишут либо метод ветвей и границ, либо записывают задачу с терминах линейного программирования и пытаются найти целочисленное решение. Кстати, второе я бы попробовал. Нужно взять какой-нибудь солвер типа Gurobi и проверить.
Есть простенькие приближенные эвристики. Например, отсортируем все ребра графа и будем их пробовать вставлять в наш путь в порядке возрастания веса. Пишут, что такое дает на практике ошибку по 15-20%.