Best Path Algorithm Question!

You know it well. The Dijkstra algorithm isn't just passing through every point, it's just the fastest way to get to the destination.

If you have to go through everything, this is the Traveling Salesman problem, TSP. However, there is no need to return to the original point, so it is a slightly modified traveling salesman problem.

This is mathematically equivalent to NP hard, and there is no algorithm for finding the best in one go except for beating up the number of cases.

If it were me, I would solve it like this.

 - [Cost to the node you are visiting] + [Minimum pass cost out of the total pass cost] *[Nodes remaining] >= If V, the full number is yellow.

- If the node you're visiting is a node that just comes in and there's no way out

If the cost is less than V, we have visited all nodes through the conditions of 5, update V and visit all the remaining cases with the improved V from now on.

If there are no more combinations, exit. V and its path found so far are the best paths.

H = { [Minimum pass cost of all pass costs]* [Nodes remaining]} is the part that predicts the length of the path that remains most optimistically, and if you improve this part, it will perform better. For example, if you have a list of total pass lengths, you can sort it out, take a small ordered list, make an accumulated list, and instead of H, you can take the elements of the list that corresponds to the number of nodes left and add them.

The point is, how quickly do you judge a budding yellow guy and cut him off in the middle without searching all the way through?

Other than that, if you could squeeze it using multi-core, it would also dramatically reduce time.