Hi! another CS student here...

Are you aware of D* Lite? It's an algorithm for this problem that works simillary to A* (uses same heuristics), but can be much faster in your use case -> it's designed to handle graph that changes while it is traversed.

So, if you find a path and something changes ...