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.

Answer 2

I think it might be worth while just simply writing which vertices are odd and then find which combo of them will lead to the least amount of extra time (if the weights are for times or distances) then the total length will be every edge weight plus the extra. For example, if the odd order vertices are A,B,C,D try AB&CD then AC&BD and so on. (I'm not sure if this is a specifically named method, it just worked for me). edit: just realised this mostly only works for undirected graphs.

Answer 3

I doubt that it's optimal, but you could do a queue based search assuming the graph is guaranteed to have a cycle. Each queue entry would contain a list of nodes representing paths. When you take an element off the queue, add all possible next steps to the queue, ensuring you are not re-visiting nodes. If the last node is the same as the first node, you've found the minimum cycle.

Answer 4

what you are looking for is called "Eulerian path". You can google it to find enough info, basics are here And about algorithm, there is an algorithm called Fleury's algorithm, google for it or take a look here

Answer 5

The special case in which the network consists entirely of directed edges can be solved in polynomial time. I think the original paper is Matching, Euler tours and the Chinese postman (1973) - a clear description of the algorithm for the directed graph problem begins on page 115 (page 28 of the pdf):

When all of the edges of a connected graph are directed and the graph is symmetric, there is a particularly simple and attractive algorithm for specifying an Euler tour...

The algorithm to find an Euler tour in a directed, symmetric, connected graph G is to first find a spanning arborescence of G. Then, at any node n, except the root r of the arborescence, specify any order for the edges directed away from n so long as the edge of the arborescence is last in the ordering. For the root r, specify any order at all for the edges directed away from r.

This algorithm was used by van Aardenne-Ehrenfest and de Bruin to enumerate all Euler tours in a certain directed graph [ 1 ].