How to Find a Vertex That Minimizes Total Distance in a Graph

A common meaning of “minimizing sum of distances” in graph theory is to find a vertex whose total distance to all the other vertices is as small as possible. This vertex is called a graph median. The distances are shortest-path distances, not the lengths of arbitrary routes.

The exact answer depends on the graph: there may be one minimizing vertex or several. Here is how to define the objective and find its minimizer in an unweighted graph, with a faster method for trees.

Define the distance-sum objective

Let $G=(V,E)$ be a connected graph with $n$ vertices. Write $d(v,u)$ for the length of a shortest path between vertices $v$ and $u$, measured in number of edges. For each candidate vertex $v$, calculate

$$S(v)=\sum_{u\in V} d(v,u).$$

Including $u=v$ does not change the sum because $d(v,v)=0$. A graph median is any vertex in

$$\operatorname*{arg\,min}_{v\in V} S(v).$$

There can be ties. The minimum value is the smallest total distance; the vertices attaining it are the medians.

This is different from the graph center. A center minimizes the greatest distance to any vertex, while a median minimizes the sum of all distances. One favors a small worst-case distance; the other favors a small overall total.

Find a median in an unweighted graph

For each vertex, run breadth-first search (BFS). BFS computes shortest-path distances in an unweighted graph. Add the distances it returns, then compare the totals.

A straightforward procedure is:

1. Choose a vertex $v$.
2. Run BFS starting at $v$ and record the distance to every vertex.
3. Add those distances to obtain $S(v)$.
4. Repeat for each vertex and select the smallest sum.

One BFS takes $O(n+m)$ time, where $m$ is the number of edges. Repeating it from all $n$ vertices takes $O(n(n+m))$ time. This works for general connected, unweighted graphs. If edges have nonnegative weights, use Dijkstra’s algorithm from each vertex instead; the relevant distance is then the minimum total edge weight along a path.

Worked example: a tree with a branch

Consider the tree with edges

$$1\!-2,\quad 2\!-3,\quad 3\!-4,\quad 4\!-5,\quad 3\!-6.$$

It is a path from 1 to 5, with an extra leaf 6 attached to 3. Adding the distances from each vertex gives:

Vertex $v$	Distances to the other five vertices	$S(v)$
1	$1,2,3,4,3$	13
2	$1,1,2,3,2$	9
3	$2,1,1,2,1$	7
4	$3,2,1,1,2$	9
5	$4,3,2,1,3$	13
6	$3,2,1,2,3$	11

Vertex 3 is the unique median, because its distance sum, 7, is the smallest. Notice that vertex 3 is also the tree’s center here, but that need not be true for every graph.

A faster method for trees

For a tree, you can calculate all distance sums without running BFS from every vertex. Root the tree anywhere and first compute $S(r)$ for the root $r$. Then move from a parent $p$ to a child $c$. Let $s$ be the number of vertices in the subtree rooted at $c$, and let $n$ be the total number of vertices. The update is

$$S(c)=S(p)+n-2s.$$

Why? Moving from $p$ to $c$ shortens the distance by one for each of the $s$ vertices in $c$’s subtree, and lengthens it by one for each of the other $n-s$ vertices. The net change is $(n-s)-s=n-2s$.

In the example, root the tree at 3. Its distance sum is $S(3)=7$. The subtree containing vertex 2 and vertex 1 has size 2, so

$$S(2)=7+6-2(2)=9.$$

The subtree rooted at 6 has size 1, giving $S(6)=7+6-2(1)=11$. Applying the same update throughout the tree produces every total. A traversal computes subtree sizes and distance sums in $O(n)$ time.

Common mistakes

• Using the longest distance instead of the sum. That finds a center, not a median.
• Counting routes instead of shortest paths. The distance between two vertices is the length of a shortest path.
• Assuming the minimizer is always unique. Symmetry can produce multiple medians.
• Ignoring disconnectedness. If the graph is disconnected, some distances are infinite or undefined, so the ordinary finite-sum problem needs a convention. Usually the problem is restricted to connected graphs or handled separately by component.
• Confusing graph medians with median graphs. A median graph is a separate graph class defined by a property of shortest paths; it is not simply any graph with a distance-sum minimizer.