Algorithm to cover all edges given starting node

Question

Working on an algorithm for a game I am developing with a friend and we got stuck. Currently, we have a cyclic undirected graph, and we are trying to find the quickest path from starting node S that covers every edge. We are not looking for a tour and there can be repeated edges.

Any ideas on an algorithm or approximation? I'm sure this problem is NP-hard, but I don't believe it's TSP.

Ferren

just checking, by quickest do you mean shortest, i.e. the one with fewest edges? – Oakley

It has to cover all edges, but using the shortest path from the starting node, it's a tree like graph so you may have dead ends that you must repeat edges to backtrack – Ferren

Just do DFS if it's a tree? – Acquiescence

DFS would be great if we were searching for a goal node, but I don't see how it would help for determining the shortest path covering all edges – Ferren

Is it exactly a tree? In that case, if you don't stop the DFS before every node is visited, it will visit every edge at least once. – Acquiescence

Answer 1

Route Inspection

This is known as the route inspection problem and it does have a polynomial solution.

The basic idea (see the link for more details) is that it is easy to solve for an Eulerian path (where we visit every edge once), but an Eulerian path is only possible for certain graphs.

In particular, a graph has to be connected and have either 0 or 2 vertices of odd degree.

However, it is possible to generalise this for other graphs by adding additional edges in the cheapest way that will produce a graph that does have an Eulerian path. (Note that we have added more edges so we may travel multiple times over edges in the original graph.)

The way of choosing the best way to add additional edges is a maximal matching problem that can be solved in O(n^3).

P.S.

Concidentally I wrote a simple demo earlier today (link to game) for a planar max-cut problem. The solution to this turns out to be based on exactly the same route inspection problem :)

EDIT

I just spotted from the comments that in your particular case your graph may be a tree.

If so, then I believe the answer is much simpler as you just need to do a DFS over the tree making sure to visit the shallowest subtree first.

For example, suppose you have a tree with edges S->A and S->A->B. S has two subtrees, and you should visit A first because it is shallower.

The total edges visited will equal the number of edges visited in a full DFS, minus the depth of the last leaf visited, which is why to minimise the total edges you want to maximise the depth of the last leaf, and hence visit the shallowest subtree first.

Baywood

Answer 2

This is somewhat like the Eulerian Path. The main distinction is that there may be dead-ends and you may be able to modify the algorithm to suit your needs. Pruning dead-ends is one option or you may be able to reduce the graph into a number of connected components.

Isaisaac

Answer 3

DFS will work here. However you must have a good evaluation function to prun the branch early. Otherwise you can not solve this problem fast. You can refer to my discussion and implementation in Java here http://www.capacode.com/?p=650

Detail of my evaluation function My first try is if the length of the current path plus the distance from U to G is not shorter than the minimum length (stored in minLength variable) we found, we will not visit U next because it can not lead a shorter path.

Actually, the above evaluation function is not efficient because it only works when we already visit most of the cities. We need to compute more precise the minimum length to reach G with all cities visited.

Assume s is the length from S to U, from U to visit G and pass all cities, the length is at least s’ = s + ∑ minDistance(K) where K is an unvisited city and different from U; minDistance(K) is the minimum distance from K to an unvisited state. Basically, for each unvisited state, we assume that we can reach that city with the shortest edge. Note that those shortest edges may not compose a valid path. Then, we will not visit U if s’ ≥ minLength.

With that evaluation function, my program can handle the problem with 20 cities within 1 second. I also add another optimization to improve the performance more. Before running the program, I use greedy algorithm to get a good value for minLength. Specifically, for each city, we will visit the nearest city next. The reason is when we have a smaller minLength, we can prun more.

Hygroscopic