Является ли кратчайший гамильтонов путь NP-трудным?

Я предполагаю, что проблема SHP - это проблема Гамильтона на графе, взвешенном по ребрам. Это NP-трудный, потому что он по крайней мере так же сложен, как проблема Гамильтона. Предположим, у вас есть алгоритм для решения проблемы SHP, затем вы применяете алгоритм к взвешенному графу со всеми весами ребер, равными 1, он решит гамильтонову проблему с той же временной сложностью.

TSP требует возврата к исходной вершине, и вы можете посетить каждую вершину несколько раз. SHP запрашивает путь, который посещает каждую вершину ровно один раз.