Minimal path - all edges at least once

Question

I have directed graph with lot of cycles, probably strongly connected, and I need to get a minimal cycle from it. I mean I need to get cycle, which is the shortest cycle in graph, and every edge is covered at least once.

I have been searching for some algorithm or some theoretical background, but only thing I have found is Chinese postman algorithm. But this solution is not for directed graph.

Can anybody help me? Thanks

Edit>> All edges of that graph have the same cost - for instance 1

Answer 1

Take a look at this paper - Directed Chinese Postman Problem. That is the correct problem classification though (assuming there are no more restrictions).

If you're just reading into theory, take a good read at this page, which is from the Algorithms Design Manual.

Key quote (the second half for the directed version):

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.