I am looking for an algorithm that, given a graph, finds the shortest (or approximately shortest) path that crosses all edges at least onces. (Multiple times crossing an edge is allowed!)

The graph is connected and undirected. All edges have a weight of 1.

Unfortunately I do not have much background in graph theory. I need the algorithm for a line following robot. The robot drives on a field like this image: http://mathforum.org/alejandre/magic.square/4x4grid.gif The robot can move on the black lines. However some edges are blocked. I need an algorithm to find a route that determines a path that crosses all the non-blocked edges at least once. (It has to find a certain object placed on one of the edges.) I modeling the grid as a graph. The nodes are the intersections of the black lines. The edges are the black lines between them.

I have been searching for algorithms that - given a graph - finds a route going through all the edges (an Eulerian path). However I couldn't find an algorithm that allows multiple times crossing an edge. This is necesarry because there are notes having an even number of edges.

Thanks in advance!

  • $\begingroup$ Do you want an efficient algorithm? Surely you could enumerate all paths in the graph and then sort by length. ;) $\endgroup$ – Neal May 29 '16 at 22:21
  • $\begingroup$ How can a path "cross" an edge? $\endgroup$ – bof May 29 '16 at 22:22
  • $\begingroup$ Possible duplicate of stackoverflow.com/questions/2359078/… $\endgroup$ – Eric Towers May 29 '16 at 22:25
  • $\begingroup$ @Neal Thank for your response. It has to be reasonable efficient. It has to be solved by a computer script (in C) in a few seconds with a graph of 25 nodes, each having 4 edges at max. $\endgroup$ – Kevin May 29 '16 at 22:32
  • $\begingroup$ @Eric Thanks, it is similar indeed. The difference is that the end location doesn't matter, as long as it passes each edge. $\endgroup$ – Kevin May 29 '16 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.