基本上，我需要在图中有一条最短路径，覆盖所有顶点并返回源。任何顶点的重复都是可以的，只要它是最短路径。
我的算法从源头开始。我运行 dijkstra 算法来找到最短路径。然后我选择最小的加权未到达顶点并再次运行 dijkstra 作为所选顶点作为源并继续执行直到所有顶点完成。然后从最后一个顶点再次使用 dijkstra 找到返回原始源的最短路径。
我试过了，但似乎失败了，我找不到原因。
问问题
638 次
2 回答
1
谷歌旅行商问题，找到从源头开始覆盖所有顶点的最短循环。旅行商的代码也不难实现。
于 2015-04-22T09:50:57.073 回答
0
因为任何顶点都可以被更多地访问，一旦你基本上在图中寻找最短的封闭步行。您的方法的问题是 dikstra 只会找到从所选节点返回源的最短路径。这将产生一个星型解决方案，其中您有多个从源顶点出来的路径。这可能比步行更长。
正如文森特所说，这是一个 NP 问题，但您可以尝试使用随机游走算法来实现它。或查看旅行推销员步行问题 (http://dspace.mit.edu/handle/1721.1/33668)
于 2012-10-30T15:31:54.500 回答