我有一个有很多环的有向图，可能是强连通的，我需要从中得到一个最小环。我的意思是我需要得到循环，这是图中最短的循环，并且每条边至少被覆盖一次。
我一直在寻找一些算法或一些理论背景，但我唯一找到的是中国 postman 算法。但是这个解决方案不适用于有向图。
有人能帮帮我吗？谢谢
编辑>> 该图的所有边都具有相同的成本 - 例如 1
最佳答案
看看这篇论文 - Directed Chinese Postman Problem .这是正确的问题分类(假设没有更多限制)。
如果您只是阅读理论，请仔细阅读 this page ，来自算法设计手册。
重点引述(导引版下半部分):
The optimal postman tour can be constructed by adding the appropriate edges to the graph G so as to make it Eulerian. Specifically, we find the shortest path between each pair of odd-degree vertices in G. Adding a path between two odd-degree vertices in G turns both of them to even-degree, thus moving us closer to an Eulerian graph. Finding the best set of shortest paths to add to G reduces to identifying a minimum-weight perfect matching in a graph on the odd-degree vertices, where the weight of edge (i,j) is the length of the shortest path from i to j. For directed graphs, this can be solved using bipartite matching, where the vertices are partitioned depending on whether they have more ingoing or outgoing edges. Once the graph is Eulerian, the actual cycle can be extracted in linear time using the procedure described above.
关于algorithm - 最小路径 - 所有边至少一次，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2359078/