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!