Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Why does your first example path end in M-I-J? You have already visited I and J earlier. –  Fixee Aug 3 '11 at 0:10
    
Perhaps there is something obvious that I am not getting. How is this even a tree problem? –  anon Aug 3 '11 at 0:20
    
This doesn't answer your question, but a shorter path is given by "A-B-C-D-E-F-G-H-L-K-J-I-M" (with a weighted cost of $56$). –  JavaMan Aug 3 '11 at 0:22
    
@Fixee: yes, I should have finished at H-I-M, with a total weight of 61. thanks for taking note of that. anon: It is a graph problem, I believe. DJC: thanks –  Veehmot Aug 3 '11 at 0:45
1  
The title could be more informative. –  lhf Aug 3 '11 at 2:00
show 2 more comments

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
I don't think this is simply MST: for MSTs there is no notion of cost for a single path visiting all nodes. –  Fixee Aug 3 '11 at 0:13
    
True, I did have a suspicion my answer was somewhat premature. –  Tilo Wiklund Aug 3 '11 at 0:46
    
Thanks, I'm looking into Kruskal's Algorithm and trying to do a simple application to implement it and prove if it is useful. –  Veehmot Aug 3 '11 at 1:58
    
Thanks! I looked into both Kruskal and Prim's and ended up with the former. But as you told, it doesn't take into account a path, just return the edges. But still is a good aproximation. I'm still trying a brute force method. –  Veehmot Aug 5 '11 at 3:29
    
I made a little demo to show my approach: youtube.com/watch?v=VbSwwos4R2E –  Veehmot Aug 5 '11 at 3:49
add comment

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.

share|improve this answer
    
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. –  Veehmot Aug 3 '11 at 1:59
add comment

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

share|improve this answer
    
Thanks. I have already read about TSP, but I think is different enough to have a different solution applied. Apart from the 4 degree restriction, the TSP problem can travel to any point, that is every city is connected to each other. In my example, there are specific "cities" linked together. –  Veehmot Aug 3 '11 at 2:02
    
You can convert your problem to the TSP by adding virtual edges which correspond to the shortest multi-step path between each pair of nodes. –  Kevin Reid Aug 3 '11 at 2:34
    
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. –  Gerry Myerson Aug 3 '11 at 2:58
add comment

You might find the discussion here of interest: http://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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.