2. Devise an algorithm (write down a pseudocode or clearly describe the steps of
ID: 3583036 • Letter: 2
Question
2. 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 shortest path from one user to the other on the directed graph that represents R
Explanation / Answer
This can be explained using Djikstra algorithm:
Baiscs of the Djikstra then we will head on to the pseudocode to find shortest distance between any 2 users in Facebook Graph R:
Using the Dijkstra algorithm, it is possible to determine the shortest distance (or the least effort / lowest cost) between a start node and any other node in a graph. The idea of the algorithm is to continiously calculate the shortest distance beginning from a starting point, and to exclude longer distances when making an update. It consists of the following steps:
Graph = R // initializing R to variable Graph function Dijkstra(Graph, source):
Graph = R // initializing R to variable Graph function Dijkstra(Graph, source):
for each vertex v in Graph: // Initialization dist[v] := infinity // initial distance from source to vertex v is set to infinite previous[v] := undefined // Previous node in optimal path from source dist[source] := 0 // Distance from source to source Q := the set of all nodes in Graph // all nodes in the graph are unoptimized - thus are in Q while Q is not empty: // main loop u := node in Q with smallest dist[ ] remove u from Q for each neighbor v of u: // where v has not yet been removed from Q. alt := dist[u] + dist_between(u, v)Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.