CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
user1372984
user1372984

Reputation:

Algorithm - Friend of a friend

I'm just learning graph theory and I'm trying to write the code to an algorithm problem. The problem involves n group of people, each of them has at least one mutual friendship with one of the members. The problem is to find the shortest friendship link between two people. The shortest friendship link contains the fewest number of people. For example; A and B are mutual friends and B and C are mutual friends, if A and C are also mutual friends then A-C and A-B-C are friendship links between A and C but A-C is considered shorter because it involves lesser individuals.

I would like to know which graph theory algorithm(s) applies in this case and I would appreciate any recommendation of a good free internet documentation on graph theory (other than wiki).

Upvotes: 5

Views: 11783

Answers (1)

amit
amit

Reputation: 178411

For the unweighted problem of shortest path of two nodes - you can do with BFS, no need for Dijkstra's algorithm which is harder to implement and is less efficient.

Note that the main problem of BFS is space efficiency, since it runs in O(|V|) space, it can be partially solved with a trade-off with DFS called Iterative Deepening DFS. It will also be optimal, but will consume less space (at the cost of extra time).

It doesn't seem to be the case, but if you can evaluate how close you are from the target - you can use A* Algorithm, which is given a good heuristic function is likely to perform faster.

Also note: If you want the shortest distance between ALL users, you can use Floyd-Warshall's algorithm

Upvotes: 8

Related Questions