You could construct two level graphs starting starting simultanously from your node and the other member's. Add layers one at a time to each.
When, after adding a new level, you find one or more nodes in both level graphs, you can stop. Each shared node gives you a least-edge path between the two start nodes. By roughly halving the depth of a simple BFS, you avoid touching k^(D-1)nodes in a graph with degree k, which is a useful trick. Whether this is "optimal" can't be said because you haven't defined optimality. In case some haven't heard the term, a level graph is formed by breadth first search in stages. First you find all nodes reachable from the start node by 1 edge traversal. This is level 1. Then find all unfound nodes reachable by 1 edge from level 1 nodes. This is level 2, etc. On Sep 18, 4:04 am, bittu <shashank7andr...@gmail.com> wrote: > if you click on any orkut member's name you will notice the > relationship graph for both of you indicating through whom you are > interconnected or in certain cases you won't get this path. > > if you have to propose algorithm what would be the one ...breadth > first or depth first traversal with some modifications will help but > wouldn't be most optimum way > > Regards > Shashank Mani > Computer Science & Engineering > Birla Institute of Technology,Mesra > Cell No. +91-9166674831 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
