Reference request: Depth- (or Breadth-) first search with hints?
The Reachability Wikipedia page lists several solutions, although the only one which works for general graphs involves computing the transitive closure, which it sounds like you want to avoid.
This is additionally for exact computations of the path.