实施特定的旅行推销员变体
我正在寻找一种算法（C / C ++ / Java – 无所谓），它将解决一个问题，即找到图形的2个节点（A和B）之间的最短路径。 问题是路径必须访问某些其他给定节点（城市）。 一个城市可以不止一次访问。 路径示例（ A- HDCE- F – G – F – B ）（其中A是源，B是目的地，F和G是必须访问的城市）。
我认为这是旅行推销员问题的变体，但我无法找到或编写基于我的搜索的工作算法。
我试图找到一个解决方案，从这些主题开始，但没有任何运气： https ： //stackoverflow.com/questions/24856875/tsp-branch-and-bound-implementation-in-c和访问多个城市的TSP的变化
将问题轻松减少到TSP将是：
- 对于“必须访问”的每个
(u,v)，找到它们之间的距离d(u,v)。 这可以使用Floyd-Warshall算法有效地找到所有最短路径。 - 创建一个新图形G’，仅包含那些节点，所有边都存在，距离计算在（1）上。
- 运行标准TSP算法来解决简化图上的问题。
我认为除了amit的答案之外，你还需要增加A或B作为端点的边缘成本足够的数量（图表的总成本+ 1可能就足够了）以确保你不要最终得到一条通过A或B的路径（而不是以A和B结尾）。
A--10--X--0--B | | | | 10 | | | | +---0--Y--0--+
上述情况将导致从A到Y到B到X的路径，除非您增加A和B边的成本（减少21）。
A--31--X--21--B | | | | 10 | | | | +---21--Y--21-+
现在它从A到X到Y到B.还要确保删除任何边（A，B）（如果它们存在）。