Выбранный путь не должен заканчиваться в заданной вершине.По сути, проблема коммивояжера, за исключением того, что вершину можно посещать более одного раза.
РЕДАКТИРОВАТЬ: будет максимум 10 000 вершин и ребер
Поскольку в стандартном определении TSP решением является гамильтонов цикл (или обход), оно не должно быть оптимальным. На практике TSP - это проблема оптимизации, чтобы найти самый короткий тур, как вы его описали.
Проблема все еще NP-hard , и она решается с помощью алгоритмов, которые находят почти оптимальные решения. Это один из результатов поиска "Эвристика для задачи коммивояжера" ( pdf ).
Не уверен насчет этого, но я думаю, что это оптимально (возможно, не самая эффективная мысль): вычислите минимальный путь между каждой парой точек, а затем примените коммивояжера к этому графику.