Devise an algorithm (write down a pseudocode or clearly describe the steps of yo

Question

Devise an algorithm (write down a pseudocode or clearly describe the steps of your algorithm) that will compute the distance between every pair of registered Facebook users. Assume that you know the friends of every user. Find also the complexity of your algorithm as a function of n, the number of registered users in Facebook. Hint: Let R be the friendship relation defined on the set of all Facebook users. Hence R contains all pairs of Facebook friends. The distance between two users is then given by the length of the shorthest path from one user to the other on the directed graph that represents R.

Explanation / Answer

Mate, it is not complicated at all. U just need to connect all friend of each user to that user to form a graph, each user is a vertex, and every edge connect his friend to him directly and then use graph search (All pairs shortest path is the fastest method) algorithm on the formed graph. Ask if u have any questions.

So:
1. Initialise graph object (single node)
2. Connect all friends nodes to the every user directly. (then u will get extrordinary huge graph)
3. Run Floid-Warshall algorithm, assuming that every edge has a unit weight. (u can use any graph search algorithm. (All pairs shortest path algorithms - the fastest way T(n) = O(vertexes^3) 

So, Floid-Warshall algorithm:
Let dist(k,i,j) be the the length of the shortest path from i and j that uses only the vertices as intermediate vertices.
The following recurrence:
k = 0 is our base case - dist(0,i,j) is the length of the edge from vertex i to vertex j if it exists, and otherwise.
dist(k,i,j) = min(dist(k - 1,i,k) + dist(k - 1,k,j),dist(k - 1,i,j)): For any vertex i and vertex j, the length of the shortest path from i to j with all intermediate vertices simply does not involve the vertex k at all (in which case it is the same as dist(k - 1,i,j)), or that the shorter path goes through vertex k, so the shortest path between vertex i and vertex j is the combination of the path from vertex i to k, and from vertex k to j.
After N iterations, there is no need anymore to go through any more intermediate vertices, so the distance dist(N,i,j) represents the shortest distance between i and j.

Pseudocode for Floid-Warshall(for reference):
for i = 1 to N
   for j = 1 to N
      if there is an edge from i to j
        dist[0][i][j] = the length of the edge from i to j
      else
        dist[0][i][j] = INFINITY

for k = 1 to N
   for i = 1 to N
      for j = 1 to N
         dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.