Are there any pathfinding algorithms that take customized rules into account when determining the shortest path?
Yes, this is easily solved using the A* algorithm. Once your agent has visited a particular node, increase the cost of that node to infinity and recalculate the path.