Recipe

Find the distance between two vertices

Use when: you're given a graph and two vertices u, v, and asked for d(u,v) without a search widget to slide through walk lengths for you

Goal: the exact shortest-path length between u and v, or confirmation that no path exists at all

Taught in Distance in a graph

Quick recipe

Check whether u and v share a direct edge
Rule out "different components" before searching further
Search increasing path lengths, starting at 2
Stop at the first length that works

1
Look for the edge $\{u,v\}$ in the graph's edge list. If it's there, the shortest distance is immediately $1$ .

Example

On the hub graph (edges $A\text{-}C$ , $B\text{-}C$ , $C\text{-}D$ , $C\text{-}E$ , $A\text{-}B$ , $D\text{-}E$ ), checking $\{A,D\}$ against this list finds no such edge, so $d(A,D) \neq 1$ .

Why: a direct edge is a path of length $1$ by itself, so it's always worth ruling out before searching any further.
2
Confirm $u$ and $v$ can reach each other at all, tracing outward from $u$ the way Section 3's components already do.

Example

On the hub graph, $A$ reaches $C$ , and $C$ reaches $D$ , so $D$ is reachable from $A$ . On a different graph with edges $\{A,B\}, \{B,C\}, \{D,E\}$ and an isolated $F$ , $A$ can never reach $D$ at all, so $d(A,D) = \infty$ there.
- no chain of edges from $u$ ever reaches $v$ — $d(u,v) = \infty$ , stop here
- some chain of edges from $u$ reaches $v$ — continue to Step 3
Why: no walk of any length, however long, can cross between two different components, so this check has to come before a length-by-length search.
3
Try to build a path of length $2$ from $u$ to $v$ , through one intermediate vertex, using real edges and no repeated vertex. If none exists, try length $3$ , and so on.

Example

$A, C, D$ uses real edges $\{A,C\}$ and $\{C,D\}$ , and it never repeats a vertex, so it's a genuine path of length $2$ from $A$ to $D$ .

Why: the shortest walk between two vertices is always a path, so searching path lengths in increasing order is guaranteed to hit the true shortest one first.
4
The smallest $k$ for which a genuine $u$ - $v$ path of length $k$ exists is $d(u,v)$ ; no longer length needs to be checked once one is found.

Example

Length $2$ worked on the very first try for $A,D$ above, so $d(A,D)=2$ with no need to search length $3$ or beyond.

Why: distance is defined as the shortest path length, so the first length that produces a valid path is, by construction, the answer.

Common mistakes

Searching path lengths without first ruling out "no path exists at all," and searching forever on a disconnected pair.
Allowing a repeated vertex while building a candidate path, which turns it into a walk instead of a genuine path.
Stopping at the first walk found instead of the first path found, when they aren't the same length.
Forgetting to check the direct edge first and starting the length search at $2$ unnecessarily.