I have a feature where a client can draw on a map and I will automatically snap what they drew to the roads they were likely trying to draw on.
To do this, I take the geometry of what they drew on the map and grab all of the road segments whose geometry falls under the drawn geometry, after factoring in a buffer region.
To decide what roads they were probably trying to draw on, I need to find the longest (by total road distance) contiguous sequence of road segments that can be formed using the segments retrieved.
This problem is essentially the problem of finding the heaviest (largest total weight) edge-simple (it is fine to revisit an intersection multiple times, but each road segment should only be traversed at most once) path in an undirected edge-weighted (length of the road segment) cyclic graph.
I know that this is NP-hard. That is fine, I just need to figure out what my best option for an algorithm is. I detailed what I am trying to do in case the problem space might lend itself to some algorithms more than others.
My question is essentially the same as How to find the longest (heaviest) trail in an undirected weighted graph?, HOWEVER, as the answers that question received boiled down to 'it's NP-hard', I would like to request recommendations for algorithms, even though they will not be polynomial time.
I have tried looking elsewhere for information on longest/heaviest simple paths, but most of what I can find simply states that it is NP-hard and does not offer any algorithmic leads. Additionally, I can find virtually nothing talking about longest/heaviest edge-simple paths, so I have no idea if I can use an algorithm designed for node-simple paths with an adaptation, or if the solution spaces are entirely separate.