Finding out paths in a graph of 175K nodes

Question

I am facing a problem in big data analysis, where I am finding out paths using Dijkstras algorithm for a graph with more than 175K nodes. But the problem is that I do not know for a particular source and destination if a path exists or not. I have to do this for about 1000 sources and destinations. But I cannot pick them randomly, as I am not sure if a path exists between them or not. I am not sure how to handle this. One execution of algorithm in MapReduce enviorment take about 15 mins time locally. So, trial and error is not an option. Only we I can find about at least 1000 sources and destinations is to find cycles(?) or strongly connected components? Is this correct ? I hope my problem is clear to understand.

I am basically looking for finding say 1000 pairs of sources and destinations for which a path exists in a graph of that size

Answer 1

I would suggest randomly picking 1000 source nodes, and then for each node run Breadth-First-Search until you've visited k nodes. Then, pick the next node that you would visit and set that as the destination for that source.

With this method, you're guaranteed that each destination is reachable from that source.