I have a suggestion which is quite different from those you already have. Each path is initialized toĩ edgeCost(i,j) or infinity if there is no edge between i and j.ġ6 path = min ( path, path+path ) At each step in the algorithm, path is the shortest pathĨ from i to j using intermediate vertices (1.k−1). The pseudocode from Wikipedia is: 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to jģ Also assume that n is the number of vertices and edgeCost(i,i) = 0ħ /* A 2-dimensional matrix. It is a nice example of dynamic programming and is quite simple to implement. To find the shortest paths between all users you'll have to use something like Floyd-Warshall. There may be several paths between them, and Dijkstra takes care of noting when it found a shorted path than another that was found before. Simple DFS for finding all users N nodes away from your userĭijkstra or similar should be used if you want to find the shortest path between two users.Graph connectivity for the connectivity.This is the only method of solving six-degrees of separation (of those mentioned so far) that will work in practice. In practice, these numbers would be much smaller, since often two of your friends are also friends with each other. If each person has an average of 100 friends, this could require looking at up to about 2,020,200 users, as opposed to the 1,010 billion for Dijkstra's algorithm. If none, then add the users 2-steps from UserX and intersect then add users 2-steps from UserY and intersect etc.
The fastest O(n) algorithm for six-degrees of separation would probably be finding the sets of all users 1-step away from UserX and UserY, and finding the intersection of those two sets. Stop after you've reached your destination for Problem #1, stop after the shortest path is > 3 for Problem #2. You can call it "Dijkstra's algorithm with all edges having weight 1," or "breadth-first search."Įssentially, starting at the first node, visit all its relatives then mark them all as visited, record the shortest path to each (the shortest path to them + the edge you just traversed), and repeat for each of them. These questions are so closely related that the same algorithm actually solves both of them. For UserX,calculate all users that is no more than 3 steps away.There is an edge between any two users who know each other.
0 kommentar(er)
