algorithm - 给定起始节点和结束节点，覆盖图中所有节点的最短路径

Question

我正在尝试解决一个问题，其中存在一个具有正加权边的无向图，并且我需要在给定起始节点和结束节点的情况下找到恰好覆盖所有节点的最短路径。此外，图是完整的(每个节点都连接到图中的所有其他节点)。我曾尝试寻找一种可以解决此问题的算法，但还没有找到可以解决此问题的算法。由于起点和终点节点的限制，这不完全是旅行商问题。我将不胜感激任何形式的帮助。

Answer 1

如果您从节点 S 开始并在 T 结束，添加一个具有零权重边的虚拟节点 D S 和 T。在此图上找到最佳的旅行商旅行，然后从旅行中删除虚拟节点以获得您的路径。

如果您想保留图的完整性属性，可以通过将具有零权重边的虚拟节点添加到 S 和 T 来实现上述功能，并且到所有其他节点的边的权重大于图中 n 最重边的权重之和。出于实际目的，这意味着将它们的权重设置为 Integer.Max 或类似的。