Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths
This is a classic problem known as &quot;reachability querying&quot;. There are various algorithms possible, with different complexities.
Unless you are working with some huge graphs and can not afford to store the index, the simplest is storing the $O(|V|^2)$ transitive closure of your graph. This can be computed quite simply with Floyd-Warshall in $O(|V|^3)$, and with a lot more effort in $O(|V||E|)$ using the methods found in Nuutila's thesis.
Now if your graphs are truly large and you can not afford to spend $O(|V|^2)$ memory you enter an academic world of dozens upon dozens of papers, each with slightly varying performance characteristics (very often incomparable, yet almost always claiming to beat the competition), and varying difficulty of implementation. I guarantee you that almost all of them will be hard to implement however.
Allow me to reproduce Table 1 from Reachability querying: an independent permutation labeling approach, a recent paper by Hao Wei et. al. Here we have as main parameters $n = |V|$, $m = |E|$, $k$ is the width of the graph, $t$ is the number of non-tree edges of the graph after a spanning tree is formed.