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!

  • 1
    Why does your first example path end in M-I-J? You have already visited I and J earlier.2011-08-03
  • 0
    Perhaps there is something obvious that I am not getting. How is this even a tree problem?2011-08-03
  • 0
    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$).2011-08-03
  • 0
    @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: thanks2011-08-03
  • 0
    @Veehmot: You can (and should) edit your question to reflect this correction (and any others you might find).2011-08-03
  • 1
    The title could be more informative.2011-08-03
  • 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.

  • 1
    I don't think this is simply MST: for MSTs there is no notion of cost for a single path visiting all nodes.2011-08-03
  • 0
    True, I did have a suspicion my answer was somewhat premature.2011-08-03
  • 0
    Thanks, I'm looking into Kruskal's Algorithm and trying to do a simple application to implement it and prove if it is useful.2011-08-03
  • 0
    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.2011-08-05
  • 0
    I made a little demo to show my approach: http://www.youtube.com/watch?v=VbSwwos4R2E2011-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
    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.2011-08-03
  • 0
    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.2011-08-03
  • 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.