Longest shortest path in an undirected unweighted graph
Sebastian Wright 
PROBLEM
I have an undirected unweighted graph and I would like to find the longest shortest path in that graph (in other words, for each two vertices I can calculate the minimal distance between them, and I want to find maximum over all those distances).
SOLUTION ATTEMPT
I've search for graph width, range, span -- but all those terms refer to something different.
$\endgroup$ 11 Answer
$\begingroup$All considered graphs are finite, simple and undirected. Let $G=(V,E)$ be such a graph on $n$ vertices.
The minimum length of the paths connecting two vertices $v_x,v_y \in V$ is called the distance between $v_x$ and $v_y$ and is denoted by $d(v_x, v_y)$. If $G$ is disconnected and $v_x$ and $v_y$ are not in the same components, we define $d(v_x,v_y)=\infty$.
The $n \times n$ - graph distance matrix $D=(d_{xy})$ consists of all graph distances from vertex $v_x$ to vertex $v_y$. The maximum value of all entries of $D$ is called the diameter of $G$.
Example: Given $G=(V,E)$. Let $V=\{v_1,v_2,\cdots,v_n\}$ and $E=\{(v_1,v_2),(v_2,v_3), (v_2,v_5),(v_2,v_4)\}$. The $(x,y)^{th}$ entry of the distance matrix $D$ of $G$ is the distance $d(v_x,v_y)$, yielding in
$$ \begin{pmatrix} 0 & 1 & 2 & 2 & 2 \\ 1 & 0 & 1 & 1 & 1 \\ 2 & 1 & 0 & 2 & 2 \\ 2 & 1 & 2 & 0 & 2 \\ 2 & 1 & 2 & 2 & 0 \end{pmatrix}$$
Now, finding the diameter using the distance matrix $D$ is easy.
Question: How do we calculate $D$?
We could use Floyd-Warshall algorithm which runs in $O(n^3)$.
But since our graphs are undirected and unweighted, we can do better. There is an algorithm by Chan solving our problem for an unweighted and undirected graph with $n$ vertices and $m$ edges in $O(nm)$.
Yamane and Kobayashi implemented an algorithm for unweighted graphs in general. Their paper contains a small list of known algorithms solving the same problem. You can find a preprint on arXiv here.
$\endgroup$
