Exactly. The only time you should be calculating paths is after the player places new roads. Repeatedly calculating paths on a fixed graph is a huge waste of time!

It’s even easier than that since each agent only needs to plans a path once, when they start their trip. After that they are simply following a cached path, removing road segments from it as they go. Most games will simply not recalculate those paths when you change the network, because it causes a lag spike every time the player makes a change, and because most routes wouldn’t end up changing. Better to just have cars ignore roads that didn’t exist when they departed, and have them vanish if they need to take a road that has since been deleted.

My graph is changing a lot, my whole environment from walls to objects is destructable and contains complex logic like access controlled doors.

Maybe your game doesn't change much. Lack of good pathfinding is what's constricting that the most. If good pathfinding existed, games in general could become more dynamic.

You could look into whether good-enough approximations exist?

Especially if the moving entities in your game aren't supposed to be omniscient. They could gradually learn about what good enough paths are.