graph-algorithm - 完整图上最便宜的成本遍历

Question

我想知道是否有一种算法：给定一个完全连接的n节点图（具有不同的权重）......会给我从节点A（起始节点）到所有其他节点的最便宜的循环，然后返回到节点 A？有没有办法改变像 Primm 的算法来完成这个？

谢谢你的帮助

编辑：我忘了提到我正在处理一个无向图，所以每个顶点的入度 = 出度。

Answer 1

你能不能不修改 Dijkstra，为你找到所有其他节点的最短路径，然后当你找到它时，返回 A 的最短路径？

Answer 2

可以试试迭代加深A星搜索算法。它总是最优的。不过，您需要定义启发式方法，这取决于您要解决的问题。

Answer 3

不需要任何这样的路径。当且仅当每个节点的入度等于其出度时，它才存在。

你想要的是最便宜的欧拉路径。找到它的问题称为旅行商问题。没有，也不可能有一个快速的算法来解决它。

编辑：再想一想：旅行推销员问题搜索恰好访问每个节点一次的旅行。您要求进行至少访问每个节点一次的游览。因此，您的问题可能只是在 P 中。不过，我对此表示怀疑。