🧠 Classroom Worksheet: Exploring Warshall's Algorithm

📘 Objective:

Understand how Warshall’s Algorithm helps answer the question: “Can I get from one node to another, even through other nodes?”

🔧 Scenario: Social Network Friend Suggestions

You’re building a simplified social network like Facebook.

Users:

• Alice
• Bob
• Carol
• Dave

Direct Friendships:

• Alice ➔ Bob
• Alice ➔ Carol
• Bob ➔ Alice
• Bob ➔ Dave
• Carol ➔ Dave
• Dave ➔ Bob

❓ Goal: Figure out who each person may indirectly know ("friend-of-a-friend") using Warshall’s Algorithm.

📂 Step 1: Adjacency Matrix (Direct Connections)

Fill this matrix with 1 (yes) or 0 (no):

↻ Step 2: Warshall's Algorithm (Transitive Closure)

Apply the formula:

R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])

Do this for k = 0 to 3 (each user).

Use extra sheets or whiteboards to update the matrix each time k changes.

✅ Final Reachability Matrix

After applying Warshall’s Algorithm, complete the matrix:

💡 Interpretation

Use the matrix to write friend suggestions:

• Alice may know: ____________
• Bob may know: ____________
• Carol may know: ____________
• Dave may know: ____________

✏️ What do large-scale social networks typically use?

Though Warshall’s algorithm is typically taught for foundational graph concepts, large-scale social networks rely on multi-layered recommendation engines that combine graph-based heuristics (e.g., mutual friends) with sophisticated machine learning. They use advanced embedding techniques (like node2vec, DeepWalk, or GNNs) to capture user similarity in a high-dimensional space. Finally, they employ distributed systems and approximate nearest neighbor searches to handle billions of users and provide real-time friend suggestions.