algorithm - TSP-Variant，可能的算法？

Question

经典的旅行商问题 (TSP) 定义之一是：

给定一个三角不等式成立的加权完全无向图，返回一条总权重最小的哈密顿路径。

在我的情况下，我不想要哈密顿路径，我需要两个众所周知的顶点之间的路径。所以公式是：

给定一个加权完全无向图，其中三角不等式成立，并且两个称为源和目标的特殊顶点返回一个最小加权路径，该路径恰好访问所有节点一次，并从源开始并结束到目的地。

我记得哈密顿路径是无向图中的路径，它只访问每个顶点一次。

对于原始问题，Christodes 算法是一个很好的近似值（最好解决方案的 3/2），是否可以针对我的情况进行修改？或者你知道另一种方式？

Answer 1

将一条边（= 道路）从目标节点添加到成本为 0 的源节点，您就有了一个 TSP（尽管三角不等式不成立）。

《追逐旅行推销员》一书中简要提到了这种技术。

Answer 2

为什么不使用 dijkstra 算法，并在每个节点上额外记录路径信息。即，在从源到该特定顶点的最短路径中传递的顶点列表。

到达终点时停止。那么你的路径将是

当前边 + 当前边的起始顶点的路径。

当前边缘是引导您到达目的地的最后一个边缘。