受此漫画启发 http://xkcd.com/173/
我知道有很多算法可以找到加权图的最小生成树，但是我一直在努力寻找任何可以找到最小生成“路径”的算法。
对于漫画，如果我们根据每对关系对每条边进行加权，那么社会最优安排将是最小跨越“路径”，即跨越所有顶点的路径。任何人都可以帮忙吗？
最佳答案
寻找最优哈密顿路径(也称为最优路径覆盖)是一个难题。 (确定是否存在任何哈密顿路径是一个 NP 完全问题。)This scholarly article除其他外，讨论了最佳路径覆盖算法。您可以在网络上搜索这些术语以查找其他资源。我不知道任何现成的代码。
顺便说一句，this question (这基本上是你的重复)清楚地解释了为什么旅行商问题不是开始的地方。
关于graph - 找到 'minimal spanning path' 的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10729534/