This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
I want to know if there is an efficient algorithm that allows me to visit every node in a planar graph with the minimum weight, 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
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
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.