So I am using A* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must-pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.
The person must visit the blue node last, which is why the distance hasn't been included for that node.
As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.
Here is where I come across a problem:
If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).
Would this not mean the person ends up traveling through all of the other must pass nodes on the graph before they even reach the first must pass node?
Are my criteria for picking the next node for the algorithm wrong?
What am I doing here that is wrong? Or is this a fault with A*?
Note: The weights on each edge are measured fairly accurately by hand with a ruler, so I doubt that is the issue.
The one question I need to be answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.