4
$\begingroup$

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

Graph Example

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!

  • 0
    @Veehmot: consider cross-posting your question to cstheory.SE; that community specializes in this kind of problem (among other things).2011-08-03

4 Answers 4

3

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.

  • 0
    I made a little demo to show my a$p$proach: http://www.youtube.com/watch?v=VbSwwos4R$2$E2011-08-05
3

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.

  • 0
    Thanks for your time, I'm reading about MST as described earlier. I will compare and test all algorithms and ideas posted here, and pick the most efficient one.2011-08-03
2

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).

  • 0
    In the TSP problem, if you assign distance $10^{100}$ to any pair of cities that you don't want connected to each other, it reduces to your problem.2011-08-03
2

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.