I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the shortest path from one node to another?
closed as unclear what you're asking by D.W.♦, Juho, Luke Mathieson, lPlant, Nicholas Mancuso May 26 '15 at 0:11
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
assuming you don't have any heuristic function about the distance to the target, a good solution that is valid is bi-directional BFS:
Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.
Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.
why is it better then BFS from the source?
assume the distance between source to target is
k, and the branch factor is
B [every vertex has B edges].
BFS will open:
1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open:
2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.
for large B and k, the second is obviously much better than the first.
NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function:
successor(v) which returns all the successors of a vertex [all vertices you can get to, within 1 step from v]. With this, only the nodes you open [
2 + 2B + ... + 2B^(k/2) as explained above] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.
In your case, the difference between BFS and bi-directional BFS, assuming 6 degrees of seperation is between developing ~
200^6 = 2.4e13 nodes, and
2*200^3=16,000,000. As you can see, bi-directional BFS needs much less nodes to be developed than the alternative.