2.1.The input is a connected, undirected graph $G$. For any two vertices $u,v$, let $d(u,v)$ denote the distance from $u$ to $v$ (i.e., the length of the shortest $u$-$v$ path). The diameter $D$ of $G$ is the maximum distance in $G$, i.e., $D = \max_{u,v} d(u,v)$. Describe an $O(mn)$-time algorithm that returns $D$, explain why it's correct, and analyze its running time.
Brute force is sufficient: we can run BFS from every vertex and keep track of the maximum distance. More specifically:
ALG(G):
diam = 0
for each vertex u:
d = BFS(G, u)
diam = max(diam, max(d))
return diam
When we run BFS from $u$, we can find the farthest distance from $u$, so running BFS from every vertex suffices. The algorithm makes exactly $n$ iterations (one per vertex), and each iteration takes $O(m+n) = O(m)$ time. (Since $G$ is connected, $n \leq m+1$.) So the total running time is $n \cdot O(m) = O(mn)$.