TSP-Вариант, возможный алгоритм?

Question

Определения классических путешествующих продавцов (TSP):

Учитывая взвешенный полный неориентированный граф, где выполняется неравенство треугольника, возвращает гамильтонов путь минимального общего веса.

В моем случае я не хочу пути Гамильтона, мне нужен путь между двумя хорошо известными вершинами. Таким образом, формулировка будет выглядеть так:

Учитывая взвешенный полный неориентированный граф, где выполняется неравенство треугольника, и две специальные вершины, называемые источником и получателем, возвращают минимальный взвешенный путь, который посещает все узлы ровно один раз и начинается с источника и заканчивается до пункта назначения.

Напомню, что путь гамильтониана - это путь в неориентированном графе, который посещает каждую вершину ровно один раз.

Для оригинальной проблемы хорошее приближение (в худшем случае 3/2 наилучшего решения) является алгоритмом Христодеса, его можно изменить для моего случая? Или ты знаешь другой способ?

Answer 1

Добавьте край (= дорога) от узла назначения к исходному узлу со стоимостью 0, и у вас есть TSP (для которого неравенство треугольника не выполняется).

В книге «В погоне за путешественником» кратко упоминается эта техника.

Answer 2

Почему вы не используете алгоритм dijkstra с дополнительным хранением книг на каждом узле для информации о пути. то есть список вершин, переданных в кратчайший путь к этой конкретной вершине из источника.

И остановитесь, когда достигнете своей конечной вершины. Тогда ваш путь будет

Путь к начальной вершине текущего края + текущий край.

где текущий край - это последний край, который ведет вас к месту назначения.