I'm facing an undirected weighted graph problem that I'm sure has been tackled many times, and I'm wondering if it has a name and existing algorithm. Edges represent value I want to capture and maximize, starting from a subgrid and expanding outward until it's not worth it any more to continue.
Let's say my starting grid is composed of nodes 3 and 5 in the image below. I want to capture the big numbered edges and avoid the small numbered edges. The best greedy move would be to 4 to capture the large 15 edge, now my grid is 3, 5 and 4. The next best move would be connecting 5 to 8 to capture the 12 edge.
Now, a greedy algorithm might not connect that huge 20 connection, since it requires a weaker move like 4 to 7 or 2 to 1 first. Could I use something like an A* or Dijkstra's? And as for a stopping point how do I capture the "cost" of expansion? Do I just calculate the length of the segments traveled and compare it to the edge value captured and subtract it from the segment's value?