Reference request: Depth- (or Breadth-) first search with hints?

Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.

Would it be possible to pre-process the graph and compute some “hints” among all nodes in the graph, such that given any node pair $s$ and $t$, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between $s$ and $t$? Therefore, the DFS or BFS will only traverse the “promising” edges to find the $s$–$t$ path. Is it a known problem?

Transitive closure could be one possible “hint”. I am wondering if there is any cheaper solution, preferably in O(n) time.

Edits: “promising” means very likely. It appears that it’s difficult to compute definitive promising edges (i.e., the edges will definitely be in an $s$–$t$ path). However, will it be possible to compute the promising edges by allowing some reasonable error?