---
title: "Distance, Radius, Eccentricity"
summary: dist on trees and graphs, the centre-of-a-tree theorem, and why two BFS passes are enough.
difficulty: core
tags: [trees, BFS, diameter]
time: n + m
space: n
prereq: [trees/bfs]
see: [trees/diameter, lca/binary-lifting]
---

:::definition label="The four distance notions"
For a connected (unweighted) graph:
- $\operatorname{dist}(u,v)$ = number of edges on a shortest path,
- $\operatorname{ecc}(v) = \max_u \operatorname{dist}(v,u)$ — how far $v$ is from the worst vertex,
- **radius** $r = \min_v \operatorname{ecc}(v)$, attained at a **centre**,
- **diameter** $d = \max_{u,v} \operatorname{dist}(u,v)$, attained at a **peripheral pair**.
Always $r \le d \le 2r$.
:::

:::proof of the sandwich
Pick a peripheral pair $a,b$ with $\operatorname{dist}(a,b) = d$ and a centre $c$. By the triangle inequality $d = \operatorname{dist}(a,b) \le \operatorname{dist}(a,c) + \operatorname{dist}(c,b) \le 2 \operatorname{ecc}(c) = 2r$, and $r \le d$ because $\min \le \max$. ∎
:::

On **trees** the picture is rigid:

:::theorem title="Structure of the centre"
The centre of a tree is a single vertex or a single edge (two adjacent vertices). Equivalently: repeatedly delete all leaves; what remains — one vertex or one edge — is the centre, the diameter path passes through it, and $\operatorname{ecc}$ is the same for both centre vertices in the edge case.
:::

:::proof
Every longest path (diameter) in a tree is unique up to reversal *between its endpoints*… more precisely: all diameters share the centre. Leaf-stripping decreases the eccentricity of every surviving vertex by exactly 1 and cannot create a new longest path, so the process ends on the set of vertices of minimum eccentricity. Since the tree has no cycle, the survivor set is connected: one vertex or one edge. ∎
:::

Algorithmically, leaf-stripping is a multi-source BFS from all leaves with a queue — $O(n)$, and it also solves "minimum height rooted tree" (LeetCode-style *find root of minimum height tree*), and the *tree centre* used as the root of a centroid-like decomposition heuristic.

## Distances between many pairs at once
Two questions that look like "run BFS $n$ times" but are not:

:::example title="Eccentricity of every vertex in a tree"
The naive $O(n^2)$ becomes two DFS passes: for each vertex the farthest vertex is an endpoint of *some* diameter — this is false in general, but for a **tree** the following DP is exact: keep `down[u]` (best distance into the subtree) and `up[u]` (best distance via the parent), then $\operatorname{ecc}(u) = \max(\text{down}, \text{up})$. Combining children needs the two largest `down` values, hence $O(n)$. The rerooting code is below.
:::

```cpp reroot.cpp
// down1[u], down2[u]: the two deepest downward paths through u
void dfs1(int u, int p) {
    for (int v : g[u]) if (v != p) {
        dfs1(v, u);
        int cand = down1[v] + 1;
        if (cand >= down1[u]) { down2[u] = down1[u]; down1[u] = cand; }
        else if (cand > down2[u]) down2[u] = cand;
    }
}
// up[u]: best path going through the parent of u
void dfs2(int u, int p) {
    for (int v : g[u]) if (v != p) {
        int via_parent = 1 + max(up[u], (down1[v] + 1 == down1[u] ? down2[u] : down1[u]));
        up[v] = max(up[v], via_parent);
        dfs2(v, u);
    }
}
// ecc[u] = max(down1[u], up[u]);  radius = min ecc;  diameter = max ecc
```

:::note title="Why the guard `down1[v] + 1 == down1[u]`"
When the best path through $u$ *is* the one coming from $v$, you must not reuse it — take the second best instead. Every rerooting DP has this "exclude the child you came from" step; getting it wrong is the most common silent bug in tree DPs, and it is exactly why keeping the two best values (not just the best) is worth the extra array.
:::

## General graphs
- All-pairs BFS: $O(nm)$ — fine for $n \le 2000$, better than Floyd's $O(n^3)$ when the graph is sparse.
- Unweighted with small integer weights: 0-1 BFS / Dial, @shortest/sparse-tricks.
- Weighted: run Dijkstra per source ($O(nm + n^2 \log n)$) or Floyd–Warshall (@shortest/floyd-warshall).
- Approximating diameter in huge graphs: two BFS passes give a $2$-approximation in *any* graph, and $O(\sqrt{\log n})$-approximation needs more machinery; the exact value needs $\tilde\Theta(nm)$ under SETH, which is the standard "you cannot do better" citation.

:::demo id="traversal" caption="Same graph: the BFS layer numbers are exactly dist(root, ·); DFS's are not. That is the whole difference between the two traversals."
:::

:::problems
- [[CSES 1132]] Tree Distances I | https://cses.fi/problemset/task/1132 | core | rerooting
- [[CSES 1133]] Tree Distances II | https://cses.fi/problemset/task/1133 | core | sum of distances
- [[CF 700B]] Connecting Universities | https://codeforces.com/problemset/problem/700/B | hard | edge contribution
:::