完整图上最便宜的成本遍历
我想知道是否有一种算法： 给定一个完全连接的 n 节点图（具有不同的权重）...会给我从节点 A（起始节点）到所有其他节点并返回到节点 A 的最便宜的循环？有没有办法改变像 Primm 这样的算法来实现这一点？
感谢您的帮助
编辑：我忘了提及我正在处理一个无向图，因此每个顶点的入度=出度。
I was wondering if there is an algorithm which:
given a fully connected graph of n-nodes (with different weights)... will give me the cheapest cycle to go from node A (a start node) to all other nodes, and return to node A? Is there a way to alter an algorithm like Primm's to accomplish this?
Thanks for your help
EDIT: I forgot to mention I'm dealing with a undirected graph so the in-degree = out-degree for each vertex.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你能不能修改Dijkstra，找到到所有其他节点的最短路径，然后当你找到它时，再找到回到A的最短路径？
Can you not modify Dijkstra, to find you the shortest path to all other nodes, and then when you have found it, the shortest path back to A?
您可以尝试迭代加深A星搜索算法。它始终是最佳的。不过，您需要定义一个启发式方法，这取决于您要解决的问题。
You can try the iterative deepening A star search algorithm. It is always optimal. You need to define a heuristic though and this will depend on the problem you are trying to solve.
不需要有任何这样的路径。当且仅当每个节点的入度等于其出度时它才存在。
你想要的是最便宜的欧拉路径。找到它的问题称为旅行推销员问题。没有也不可能有快速算法来解决这个问题。
编辑：
再想一想：旅行商问题搜索一次访问每个节点的旅行。您要求进行一次至少访问每个节点一次的游览。因此，你的问题可能只是出在 P 上。不过我对此表示怀疑。
There need not be any such path. It exists if and only if the in-degree of every node equals its out-degree.
What you want is the cheapest Eulerian path. The problem of finding it is called the Traveling Salesman Problem. There is not, and cannot be, a fast algorithm to solve it.
Edit:
On second thought: The Traveling Salesman Problem searches for a tour that visits every node exactly once. You're asking for a tour that visits every node at least once. Thus, your problem might just be in P. I doubt it, though.