Excactly. Without having thought it through, what about simply applying Dijkstra's algorithm? Its complexity (when edges are stored in a heap) is like N log N, where N is the order of magnitude of number of addresses / transactions, which seems feasible to me. But please correct me if not, as I said, I haven't really thought that through.
Dijkstra's helps to find the shortest path, but I'm not sure if it reduces the complexity at all in this case, because each edge weight is equal and thus there is no path in favor and so we'd start with the source address and visit each neighbor. If target isn't found, we'd need to visit each neighbor of each neighbor. If it's not found, each neighbor of each neighbor of each neighbor and so on. I guess that would take something like E(k^n) = k^0 + k^1 + k^2 ... steps, where k is the number of connections per node and n is the search depth.
O(n*log(n)) (n for comparison, log(n) for going deeper in a tree) is the best possible complexity for searching based on pairwise comparison, but we don't have any attribute like "this tx-path is more likely than the others" to create an order.
Please correct me if I'm wrong, this is all stuff I know only vague about.
