A* pathfinding with Multiple Agents

I've currently been learning and programming pathfinding(in Java) using the A* algorithm. A problem I've run into is when multiple entities are trying to pathfind, they both alter the previousNode(the Node that the Node being calculated on came from), messing up the algorithm, and eventually Node A will point to Node B and Node B will point to Node A.

How can I change the algorithm to either

• Not use this previousNode system that is littered throughout all of the A * algorithms(that I have seen, that is)


• Alter this system to be used concurrently

I am trying to avoid having one entity finish pathfinding, then telling the next entity to pathfinding, and so on. Like doing a wait() - notify() pair in Java.