Shortest path to draw all polyline routes in geometric network without repeating

Question

My problem is related to the "shortest path" problem, however it's slightly different in that I don't want to draw one path but to draw all paths without repeating any routes (as much as is possible). I'm trying to work out what this geometric problem is called (if it has been covered at all) in order to find an algorithm to work with.

Say there are 6 points in a network that are attached via a web of 10 edges (non-weighted). I must make a route starting form any one single point and move down every edge in any order but without repeating any of these edges. When I find myself in a position where there are no possible new edges forward I can either take one of the previously travelled edges back or I can go "off-road" directly to a new point, however these are considered "lost time". What I want is to find an algorithm (or even the name of this geometric problem) that will minimise "lost time" As I attempt to move down all routes.

An easier way to explain might be a printer that draws out all of these paths: while the printers pen is down (i.e. drawing) we are not wasting energy, however as the printers pen will not repeat any drawn lines it may have to move between points with the pen up, which we consider as wasted energy. I want to minimise energy waste.

Can anyone help point me in the right direction?

Answer 1

You need to do a perfect, minimum weight matching, done using the blossom algorithm

Find all points in your network with an odd number of edges. From these you find the distance (lost time) to all other such points. This is the input to the blossom algorithm. Once you have the perfect matching, the "lost time" edges can be added to the network and you have a network with all points having an even number of edges.