-1
$\begingroup$

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?

$\endgroup$

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.

  • $\begingroup$ What have you tried? What research have you done? What algorithms have you considered? Have you tried benchmarking any of them? We expect you to do research on your own before asking, and to show us in the question what you've tried. See cs.stackexchange.com/help/how-to-ask. The obvious answer is BFS; so what research have you done into that method? $\endgroup$ – D.W. May 18 '15 at 4:27
  • $\begingroup$ Maybe these slides are helpful. $\endgroup$ – Juho May 18 '15 at 6:28
  • $\begingroup$ @Juho thanks, those slides are really helpful. $\endgroup$ – Viacheslav Kravchenko May 18 '15 at 13:55
  • $\begingroup$ @D.W. I think this question is too easy to computer science community to do my own researches and benchmark all possible algorthms. $\endgroup$ – Viacheslav Kravchenko May 18 '15 at 14:00
  • $\begingroup$ You're saying this question should be so easy for the CS.SE answerers that you don't think you should have to do any research on your own before asking? That's not how it works. $\endgroup$ – D.W. May 18 '15 at 15:30
1
$\begingroup$

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.


Disclaimer: Most of this answer (except the last part) is copied from my answer on StackOverflow.com, as suggested in meta (and effectively applied by a mod in security.SE)

$\endgroup$
  • $\begingroup$ Thanks for the deep explanation. I was thinking about bi-directional BFS but was wondering if there are some better solutions. But it seems like BFS is the best solution in my case. $\endgroup$ – Viacheslav Kravchenko May 18 '15 at 14:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.