Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Question

Update:

This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.

http://www.youtube.com/watch?v=VbSwwos4R2E

Hi, I want to know if there is an algorithm that allows me to visit every node in a graph, revisiting allowed, each node can have up to 4 linked nodes.

I uploaded the graph drawing as an example. In that example, one good route would be:

A - B - C - D - E - F - G - H - I - J - K - L - H - I - M

Summing weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = 61

But another route, with less weight, would be:

A - B - C - D - E - F - G - H - I - M - I - H - L - K - J

Weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = 60

Of course, I want to get the path with less weight. Revisited is allowed because otherwise I can't visit all nodes.

I'm not a Mathematician myself so easy talk would be much appreciated. I'm familiar with algorithms like A* and Dijkstra, that algorithms are useful when I have a target to search, but in this case I'm not searching a particular target.

Thanks!

Answer 1

Is sounds like you want to generate a spanning tree of the graph, this is most commonly done with a depth-first or breadth-first search. Wikipedia has a short discussion of possibilities if you want to parallelise things.

Adding the consideration of weights, what you want is a minimum spanning tree, for algorithms, see, again, wikipedia.

Edit: As a good comment points out, the problem is not, given by finding a minimum spanning tree. It might still be a reasonable way to get a passable solution though.

Answer 2

A very similar problem is the Route Inspection Problem (aka the "Chinese Postman Problem"). That problem is exactly the same as yours, except that one must visit each edge rather than each node as you require.

I suspect that your variant is NP-Hard.

Strictly speaking, you asked only if "there is an algorithm" for your problem; there most certainly is: try all solutions and take the best one. Since there are a finite number of candidates, this is an algorithm.

If you want an efficient algorithm, I'm going to guess you won't find one. However, I would be pleased to be proven wrong.

Answer 3

It seems to me this is a variant on the Traveling Salesman Problem. You should have no trouble finding literature on this problem. The standard version is known to be NP-hard, which implies that no one knows a good algorithm for solving it in general (although there are very good algorithms for small instances, and very good algorithms for finding approximate solutions). Your restriction that each node have degree at most 4 may make the problem easier (but I doubt it).

Answer 4

You might find the discussion here of interest: https://stackoverflow.com/questions/5280594/travelling-salesman-with-repeat-nodes-dynamic-weights There are perhaps also ideas of interest to you in the book: The Vehicle Routing Problem, ed. Toth and Vigo, SIAM, 2002.