you will learn how to compute the shortest path between vertices in a graph.
we are working with the social graph.
Users are encoded with numbers and edges represent a "follows" relation.
We have loaded and prepared the graph data with the code in this slide.
a social network and found out that you have several mutual friends?
friends of friends, friends of friends of friends, and so on?
These features use a craft distance in their internals.
Let me introduce some definitions.
vertices where every two consequent vertices are connected by an edge.
The path length is the number of edges in the path.
the distance between two vertices is the length of the shortest path between them.
users at a distance of one are those whom I follow.
Users at a distance of two are followed by those whom I follow, and so on.
the distance to every other user in the graph.
To do so, we will run a breadth-first search from the vertex X.
Precisely, we start with annotating the vertex X with distance zero.
Then, we find all neighbors of X and annotate them with distance one.
we start with nearly annotated vertices and repeat the process.
we take the minimum because we are interested in the shortest path.
We terminate the algorithm when the distances are not changing any more.
it is equivalent to stop when there are no unvisited vertices.
Now, let me guide you through the code.
I will omit the prompt marker, perfect.
The idea is to have a mapping from a vertex to its neighbors.
let's create an initial distance mapping.
For example, let's start with vertex 12.
Now, you need to find neighbors of the vertex and update their distances.
I'm sure you know how to do this, right?
there is a pair of vertex 12 and distance 0.
there is a pair of vertex 12 and vertex 13, the neighbor vertex.
distance 0, and vertex 13.
Now, we need to perform a step to devise that vertex 13 is at a distance of 1.
Is it the final distance?
yes, but generally speaking, no.
Recall, you may have visited the vertex already.
Now, how to account for that.
You need to check if the distance was computed already or not.
So, once again, you need to join two datasets as shown in this slide.
Congratulations, you have done one iteration of the algorithm.
Now, you need to make a loop.
these helper functions for brevity, that's it.
Now, let's think about the termination criteria.
How can you check that you have visited all reachable vertices?
For example, you can check if you have reached any new vertices on the current iteration.
Their distance in this case will be equal to the iteration number.
move the iteration step inside the loop and count the number of new vertices.
you need to break the loop.
Otherwise, prepare for the next iteration by updating the search frontier.
First, Spark discards intermediate data after the computation.
from the source vertex on every iteration.
over again because it knows nothing about the key distribution of data.
We can hint how to partition the data thus avoiding reshuffles.
more detail in the next course of the specialization.
from any vertex in the graph to all other vertices.
iterative algorithms in Spark and use persistence to avoid performance issues.
a simple breadth-first search algorithm to compute distances from a given vertex.