algorithm - 最小路径 - 所有边至少一次

Question

我有很多循环的有向图，可能是强连接的，我需要从中得到一个最小的循环。我的意思是我需要得到循环，这是图中最短的循环，并且每条边至少被覆盖一次。

我一直在寻找一些算法或一些理论背景，但我发现的只有中国邮递员算法。但是这个解决方案不适用于有向图。

有谁能够帮我？谢谢

编辑>>该图的所有边具有相同的成本 - 例如 1

Answer 1

看看这篇论文 - Directed Chinese Postman Problem。这是正确的问题分类（假设没有更多限制）。

如果您只是阅读理论，请仔细阅读此页面，该页面来自算法设计手册。

关键引用（导演版的后半部分）：

最优邮递员路线可以通过向图 G 添加适当的边以使其成为欧拉来构造。具体来说，我们找到了 G 中每对奇度顶点之间的最短路径。在 G 中添加两个奇度顶点之间的路径会将它们都变为偶度，从而使我们更接近欧拉图。找到添加到 G 的最佳最短路径集简化为在奇数度顶点上识别图中的最小权重完美匹配，其中边 (i,j) 的权重是从 i 到最短路径的长度j. 对于有向图，这可以使用二分匹配来解决，其中顶点的划分取决于它们是否具有更多的入边或出边。一旦图是欧拉图，就可以使用上述过程以线性时间提取实际周期。

Answer 2

我怀疑它是否是最优的，但假设图表保证有一个循环，您可以进行基于队列的搜索。每个队列条目将包含代表路径的节点列表。当您从队列中取出一个元素时，将所有可能的后续步骤添加到队列中，确保您不会重新访问节点。如果最后一个节点与第一个节点相同，则您已找到最小循环。

Answer 3

你正在寻找的是所谓的“欧拉路径”。你可以在谷歌上找到足够的信息，基础知识在这里 关于算法，有一个算法叫做 Fleury 算法，谷歌或者看看这里

Answer 4

网络完全由有向边组成的特殊情况可以在多项式时间内求解。我认为原始论文是Matching, Euler tours and the Chinese postman (1973) - 有向图问题算法的清晰描述始于第 115 页（pdf 的第 28 页）：

当一个连通图的所有边都是有向的并且图是对称的时，有一个特别简单和有吸引力的算法来指定欧拉之旅......

在有向、对称、连通图 G 中找到欧拉之旅的算法是首先找到 G 的跨越树状结构。然后，在除树状结构的根 r 之外的任何节点 n 处，指定远离方向的边的任何顺序n 只要树状结构的边缘在排序中是最后的。对于根 r，为远离 r 的边指定任何顺序。

van Aardenne-Ehrenfest 和 de Bruin 使用该算法枚举某个有向图 [1] 中的所有欧拉游程。