У меня есть направленный взвешенный график. Он может быть подключен или не подключен, и компоненты могут быть или не быть подключены. У меня есть две цели:Поиск путей, которые охватывают каждый узел один раз в взвешенном ориентированном графе (любой язык)
По крайней мере, придумать список путей (возможно, придется быть комбинацией путей, если весь граф не подключен), который посещает каждый узел один раз и только один раз.
Если возможно, найдите кратчайший путь (или комбинацию путей в случае, если граф не подключен), который посещает каждый узел один раз и только один раз.
В настоящее время, я думаю, самый простой способ будет просто найти все компоненты связности (с использованием в глубину, не так ли?), А затем в пределах каждого компонента Recurse через каждый возможный выбор узла и сортировки по дорожкам что я остался, чтобы найти самый короткий.
Любые другие идеи?