5

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).

  • 4
    Any shortest path algorithm will suffice here. See [Dijkstra](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), or [BellmanFord](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm). – phoeagon Feb 28 '13 at 16:32
  • @phoeagon If there are missing links ,it won't, re read the question please. I think a transitive closure should do. – axiom Feb 28 '13 at 16:33
  • You say "each of them has at least one mutual friendship with one of the members" what about this set: {A-B C-D}. What if there is not a link between A and C? – Alexander Van Atta Feb 28 '13 at 16:35
  • @axiom If there is no link, then you get infinity. What's the problem? – phoeagon Feb 28 '13 at 16:36
  • @phoeagon There may be an edge A-B and one B-C. shortest path algorithm will give the answer as A-B-C. We need to add the edge A-C before we can comment. Thus the problem. This can be resolved by calculating all the powers of Adjacency matrix and taking union. `n` iterations of Dijkstra ? – axiom Feb 28 '13 at 16:37
  • @axiom If you want all pairs, transitive closure (Floyd) is obviously viable too. So is `n` iterations of Dijkstra. – phoeagon Feb 28 '13 at 16:37
  • @axiom He did not say that the pairs queried are linked! If they are, then check for this pair in the edge edge list before you return the answer. (Maybe I still don't get the question... – phoeagon Feb 28 '13 at 16:39
  • Perhaps. but plenty of hints in the comments. Should be enough for the OP. – axiom Feb 28 '13 at 16:40
  • Why bother to do a transitive closure when connectivity itself is sufficient? If you want to check for connectivity, a non-infinity return value of Dijkstra indicates it. If you want to check for direct link, look it up in the edge list. What's the problem? If pseudo-*infinity* is not enough, use a disjoint set to check for connectivity first. – phoeagon Feb 28 '13 at 16:43

1 Answers1

8

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

amit
  • 175,853
  • 27
  • 231
  • 333
  • Do you know of any heuristic functions that are effective in this case? – James_pic May 27 '15 at 08:21
  • @James_pic That's going to depend on the data you have, I am unfamiliar with a heuristic. However, have a look at this answer for even better approach to find shortest distance between one source to one target: http://stackoverflow.com/a/7220294/572670 – amit May 27 '15 at 08:24