Question: A popular conjecture is that every pair of people in the world is connected by ``six degrees of separation''. That is, no matter who you are if we tried hard enough we could find five people so that I know the first person, the first person knows the second, the second knows the third, the third knows the fourth, the fourth knows the fifth, and the fifth knows you. Say we test this conjecture by asking 10,000 people to list 40 people they know. How can we find the ``most separated'' pair?
Answer: Construct a graph with 10,000 nodes, and include directed edges from each person to all the people that person knows. Assume each edge has length 1. Now find the all-pairs shortest path matrix (using repeated squaring or Floyd's algorithm). The most separated pair will correspond to the maximum entry in the matrix.