Мне было интересно, есть ли алгоритм, который: учитывая полностью связанный граф из n узлов (с разными весами) ... даст мне самый дешевый цикл для перехода от узла A (начального узла) ко всем другим узлам и возврата к узлу A? Есть ли способ изменить алгоритм, подобный алгоритму Примма, для достижения этой цели?
Спасибо за вашу помощь
РЕДАКТИРОВАТЬ: я забыл упомянуть, что имею дело с неориентированным графом, поэтому внутренняя степень = исходящая степень для каждой вершины.
Разве вы не можете изменить Дейкстру, чтобы найти вам кратчайший путь ко всем остальным узлам, а затем, когда вы его найдете, кратчайший путь обратно к A?
Вы можете попробовать алгоритм поиска итеративного углубления в звезду. Это всегда оптимально. Однако вам необходимо определить эвристику, и это будет зависеть от проблемы, которую вы пытаетесь решить.
Такого пути быть не должно. Он существует тогда и только тогда, когда входящая степень каждого узла равна его исходящей степени.
Вам нужен самый дешевый эйлеров путь. Проблема ее поиска называется проблемой коммивояжера. Нет и не может быть быстрого алгоритма для ее решения.
Изменить: если подумать: задача коммивояжера ищет тур, который посещает каждый узел ровно один раз. Вы просите тур, который посещает каждый узел хотя бы один раз. Таким образом, ваша проблема может быть просто в P. Я сомневаюсь в этом.
