AI: Heuristic function A* search
You can use the depth as the heuristic function I guess. The start node is at depth 0, the ones adjacent to it will be at depth 1 and so on! As the function will explore nodes, the heuristic function value will gradually increase with depth and that will make the function to choose next node with more caution, so that overall cost (distance to next node + heuristic value) is least affected.

Edit: You can use powers of 2 where the exponent term will be the depth. So the start node has heuristic value 2^0 = 1, the nodes adjacent to it have heuristic value 2^1 = 2 and so on.