# What is an algorithm for finding the shortest path in a graph that crosses each edge at least once.

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!

• Do you want an efficient algorithm? Surely you could enumerate all paths in the graph and then sort by length. ;) – Neal May 29 '16 at 22:21
• How can a path "cross" an edge? – bof May 29 '16 at 22:22
• Possible duplicate of stackoverflow.com/questions/2359078/… – Eric Towers May 29 '16 at 22:25
• @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. – Kevin May 29 '16 at 22:32
• @Eric Thanks, it is similar indeed. The difference is that the end location doesn't matter, as long as it passes each edge. – Kevin May 29 '16 at 22:37