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!
Best Answer
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.