I am looking for the most efficient algorithm to find a path between every $x$ pair of nodes assuming $n$ total number of nodes in an undirected graph $G$ where $x$ is approx 1% of $n$. What are the possible algorithms and data structures I can use instead of just doing depth-first traversal from every node in $x$?
One thing to note is for my purpose, I have to find the path between random $x$ pair of nodes frequently (every epoch). So, I would tend to save more on time as compared to space.