I was watching The Mandalorian the other day when it struck me that I don't know Pedro Pascal, which is, by itself, very tragic.
But maybe I know someone, who knows someone, who knows someone, ..., who knows Pedro Pascal. Somewhere out there, there is a finite chain of introductions that connects me to him. So the important computer science question we try to solve today is: How many introductions would it take to reach him?
We accidentally have invented a graph problem!
Turn your social life into a graph
Imagine that each person on this earth is a node and any relationship or acquaintance between two people is an edge:
Alexandra ── Maria ── Sofia ── Pedro
│
└── John ── Elena ── Carlos
This is an unweighted and undirected graph.
Unweighted means that every connection counts the same. We don't care whether Maria is Sofia's best friend or someone she met once at a cafe.
Undirected means the relationship is both ways: if Alexandra knows Maria, Maria knows Alexandra.
If we strip the fluff of the original question, it kinda changes from "How do I meet Pedro Pascal?" to "Given an unweighted graph, what is the shortest path between node A and node B?", which if you are familiar with trees or graphs it sounds like a BFS (Breadth-First Search).
In code, the simplest way to represent this kind of data is an adjacency list
const graph = {
Alexandra: ["Maria", "John"],
Maria: ["Alexandra", "Sofia"],
Sofia: ["Maria", "Pedro"],
Pedro: ["Sofia"],
John: ["Alexandra", "Elena"],
Elena: ["John", "Carlos"],
Carlos: ["Elena"],
};
Make our delusions an algorithm
Unfortunately, screaming “DOES ANYONE KNOW PEDRO PASCAL?” into the void isn't an algorithm. It has no order, no memory, and no stopping condition. If you just wander from person to person picking whoever seems interesting, you can easily do this:
Alexandra → Maria → Sofia → Maria → Sofia → Maria → ...
Because the graph is undirected, Maria connects back to Sofia and Sofia connects back to Maria. Without remembering who we met already, nothing stops us from revisiting the same people forever.
So we basically need two things:
- A rule for what order to explore people in.
- A way to remember who we already visited.
That's where a queue and a visited set come in.
Breadth-first search explained
The key observation for finding the shortest path is this: check everyone one connection away before checking anyone two connections away. This is breadth-first search, and it organizes the graph into levels:
Level 0 Alexandra
│
┌──────┴──────┐
Level 1 Maria John
│ │
Level 2 Sofia Elena
│
Level 3 PEDRO 🎉
BFS will check all my direct friends (level 1), if Pedro isn't there (🥲) will check the direct friends of my direct friends (level 2) and so on. The moment Pedro is found, you know that this is the shortest possible path, because every shorter one has already been checked.
Put everything together
function introductionsAway(graph, start, target) {
if (start === target) return { degrees: 0, path: [start] };
const visited = new Set([start]);
const queue = [[start, [start]]];
while (queue.length > 0) {
const [person, path] = queue.shift();
for (const friend of graph[person] || []) {
if (visited.has(friend)) continue;
if (friend === target) {
return { degrees: path.length, path: [...path, friend] };
}
visited.add(friend);
queue.push([friend, [...path, friend]]);
}
}
return { degrees: -1, path: [] };
}
The twist: real relationships aren't equal
So far in our problem knowing someone is binary. But you and I both know that's a lie. There's a biiiig difference between:
- Maria once stood next to Pedro at an event, and
- Pedro? Yeah, we're having dinner every Thursday.
Technically, both are relationships but practically, one of them is significantly more useful to my mission.
Alexandra --2-- Maria --5-- Sofia --4-- Tessa --1-- Pedro
So let's assign every relationship an introduction cost. A close relationship has a low cost because asking for an introduction is easy. A weak acquaintance has a high cost because... well, good luck with that.
The BFS algorithm doesn't know how to handle weights. For weighted graphs, we need to move our attention to Dijkstra's algorithm.
Dijkstra's algorithm, briefly
Dijkstra's algorithm asks a slightly different question:
"What is the cheapest path from A to B?"
Instead of exploring nodes in the order we discover them, we prioritize the node who currently has the lowest accumulated cost from our starting point.
That usually means replacing BFS's regular queue with a priority queue.
Same graph, different nouns
The Pedro Pascal situation is ridiculous, i know, but the underlying problem isn't. Change what the nodes and edges represent, and suddenly the same ideas appear everywhere.
| Domain | Nodes | Edges | What "shortest path" answers |
|---|---|---|---|
| Social graph | People | Relationships | "How many introductions to Pedro Pascal?" |
| Maps / GPS | Intersections | Roads (weighted by time/distance) | "Fastest route from A to B" |
| Web crawling | Web pages | Hyperlinks | "How many clicks from this page to that one?" |
| Codebases | Modules/files | Imports/dependencies | "What breaks if I change this file?" |
| Recommendations | Users or items | Similarity/interaction strength | "What's most relevant to this user?" |
Graphs are one of those computer science concepts that you initially hate and mostly dont understand. Nodes. Edges. Traversals. Queues. But they are everywhere.. The internet itself is basically one very big graph.
And if by any chance anyone knows someone who knows someone... You know where to find me.
Top comments (16)
That is a title lol
I'm calling It making knowledge accesible - examples shouldn't be boring!
That's fair. Makes it really engaging tbh
I'm here for Pedro Pascal 👀
Aren't we all? 😂
Well @ale3oula did you meet Pedro? 😄
One day Scott, one day!
Finally, a post I can relate to!
Everyone wants to meet pedro!
I love examples like this where an algorithm suddenly stops feeling like computer science and starts feeling like something from real life 😂 The Pedro Pascal example makes BFS levels shortest paths and even the need for visited click instantly. The Dijkstra follow-up was a nice bonus too!
Thank you! CS is as fun as our imagination can make it!
Great explanation with a simple to understand example. Graph relations and Shortest path, pathfinding often get related to games, though their application goes far beyond it. Take A*, essentially, that's what you're doing, you search everyone in a direction, until you hit a dead-end and from that dead-end, you move on to the adjacent person who maybe has a better chance, until you're around the barrier. Barriers in this case being languages, regions, age, etc. None in their own is a hard barrier, but in certain instances, it's what blocks them from knowing Pedro Pascal and in turn, you. What you stated as 'yeah we walked past eachother' vs 'we're having dinner thursday' is a great way to explain nearest neighbor (in a way), the further you are from origin (Perdo), the weaker your relation to him and in turn, the weaker the chance you can act as an intermediate to reach him.
Unfortunately, I dont know him, nor know someone who knows him, etc. (atleast, I think you've got a better chance than I do), if you want to take this thought experiment to the next level, you could look at multi-origin graph traversal? Essentially, make a friend, who has a 'decent' chance of knowing someone and from them, work through to the next person, etc. Think of a teleport that takes a while. You could target him directly and just spam him on socials, though your chance of success is quite low, vs his friends group (also unlikely) vs their friends group (now you got a shot). Essentially if you're trying to get from A-Z, you're better off taking a while to get to K instead of traversing from A-K and K-Z.
This is such a fun way to take the thought experiment one step further! I especially like the idea of introducing barriers such as region or age, because the graph is no longer just about whether an edge exists, but also about how likely that connection is to actually get you closer to Pedro.
And yes, the multi-origin traversal idea is fascinating. It turns the problem into 'find the path with the highest probability of actually leading somewhere' which feels much closer to how real social networks work. I guess the probability for me to meet the actual pedro is pretty low, but maybe it worth the experiment!
Give it a go! Judge a node by it's probability to help you and it's probability to have a connection to Pedro. Eg. Find a person who lives in hollywood and liked a post about The Mandalorian, bonus points if they liked Game of Thrones too, Highest probability, if they like a post on the episodes with him, or mentioned him.
Then you make contact, build relations and search their friends group to see whose in the film industry, or adjacent.
From there on, find someone who worked for/with the same studios where he's worked.
Then from there on to someone who worked on the set when he was there.
Then from there on to any cast member or higher level production crew.
From there, to his PA/Agent/Makeup artist/dresser/etc.
Then you've got a solid contact.
It takes the closest path, to closest point to origin (him) ranked by probability (of talking to you and helping you).
That's imo the fastest way to him, if your goal is to have him like a post, or react on a comment, direct is easiest, but if you want to MEET him, you need a personal connection to intro you.
Essentially, this is how pen testing works, you find the closest vulnerable point, attack it, then work your way to the goal. If it can breach a secured server (like the classic casino attack that went through a fish tank pump), you pick the point of least resistance, closest to the goal, then work from there to the next closest vulnerability.
Thats another great example!