Compute social distance between two users

by

assuming you don’t have any heuristic function about the distance to the target, the best 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.

EDIT:

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.

More Related Contents:

  1. complexity in terms of big O
  2. Find all paths between two graph nodes
  3. Why is the constant always dropped from big O analysis?
  4. How can building a heap be O(n) time complexity?
  5. Which algorithm is faster O(N) or O(2N)?
  6. find the only unpaired element in the array
  7. Sort points in clockwise order?
  8. Determine font color based on background color
  9. Nearest neighbors in high-dimensional data?
  10. Why do we use Base64?
  11. Heap vs Binary Search Tree (BST)
  12. How to Compute OBB of Multiple Curves?
  13. Counting the adjacent swaps required to convert one permutation into another
  14. Algorithm for finding similar images
  15. design a stack such that getMinimum( ) should be O(1)
  16. Largest circle inside a non-convex polygon
  17. Generate a list of primes up to a certain number
  18. Best Fit Scheduling Algorithm
  19. Algorithm to find multiple string matches
  20. Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k
  21. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  22. How to cartoon-ify an image programmatically?
  23. Is there any fast method of matrix exponentiation?
  24. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  25. Which is faster, Hash lookup or Binary search?
  26. Finding groups of similar strings in a large set of strings
  27. Tournament bracket placement algorithm
  28. Why is bubble sort O(n^2)?
  29. Location of highest density on a sphere
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment