If the graph is directly modified by dynamic obstacles, store "time to available" in the busy edges. Then the unit walking in can check if by the time it gets there, the edge is still busy.

If obstacles are handled separately, you do the same thing except it ends up being a line intersection between nearby agents' routes. Find route intersections, estimate arrival times, if they conflict based on both units' movement speed, reroute.

Another approach would be to ignore unit as obstacles and rely on movement timeout: If I'm stuck for longer than X time, reroute.