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!