最小路径-所有边至少一次
我有很多圈的有向图，可能是强连通的，我需要从它得到一个最小的圈。我的意思是我需要得到循环，这是图中最短的循环，每条边至少被覆盖一次。
我一直在寻找一些算法或一些理论背景，但我唯一找到的是中国邮递员算法。但这种解决方案不适用于有向图。
有人能帮我吗？谢谢
Edit>>该图的所有边都具有相同的成本-例如1
回答 4
Stack Overflow用户
发布于 2010-03-02 05:18:29
看看这篇论文-- Directed Chinese Postman Problem。然而，这是正确的问题分类(假设没有更多的限制)。
如果你只是在阅读理论，可以在this page上好好读一读，它来自算法设计手册。
关键引述(后半部分为定向版本)：
最优邮递员环游图可以通过在图G上添加适当的边来构造，从而使其成为欧拉图。具体地说，我们找到G中每对奇数度顶点之间的最短路径。在G中的两个奇数度顶点之间添加一条路径会使这两个顶点都变为偶数度，从而使我们更接近欧拉图。找到最短路径的最佳集合以添加到G中归结为在奇数度顶点上识别图中的最小重量完美匹配，其中边(i，j)的权重是从i到j的最短路径的长度。对于有向图，这可以使用二部匹配来解决，其中顶点的划分取决于它们有更多的入边或出边。一旦图是欧拉的，就可以使用上面描述的过程在线性时间内提取实际的循环。
Stack Overflow用户
发布于 2010-03-02 05:17:00
我怀疑它是否是最优的，但你可以做一个基于队列的搜索，假设图肯定有一个循环。每个队列条目将包含表示路径的节点列表。当您从队列中删除一个元素时，请将所有可能的后续步骤添加到队列中，确保您不会重新访问节点。如果最后一个节点与第一个节点相同，则已找到最小周期。
Stack Overflow用户
发布于 2010-03-02 05:21:48
你要找的东西叫做“欧拉路径”。你可以谷歌它来找到足够的信息，基础是here和关于算法，有一种算法称为弗勒里的算法，谷歌为它或看看here
https://stackoverflow.com/questions/2359078
复制相似问题
腾讯云开发者
