Add edges to undirected graph to make connected and minimize longest path
Clearly, the number of added edges is one less than the number of connected components in the graph, since we can decrease this number by one by adding an edge and we seek the minimum number of added edges.

The trick is to add the edges between central vertices of the connected components. A central vertex of a connected  component is a vertex that has minimum distance to the farthest vertex to this vertex in the component (we call this distance the eccentricity). So it is a vertex that minimises the eccentricity.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $G_1, \dots, G_l$. Note that the task is to add $l-1$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $l$ by one until it gets to the value 1.

After we found the connected component we find a central vertex in each of them (central vertices might not be unique but we can choose any of them). We keep for each component a central vertex and the value of its eccentricity. Now in each step we combine to graphs, we distinct two cases.
- The minimum eccentricities are equal, then any of the two central vertices can be chosen as a central for the new graph and the new eccentricity is the previous one plus one. (Try to prove the correctness and optimality of this statement).
- The minimum eccentricities differ. Keep the central with the greater eccentricitiy. Its eccentricity does not change. (Also try to prove this).

The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $l-1$ steps.

The correctness of the previous two cases implies the correctness of the algorithm and that it does not matter in which order you process the components. Hence we get a total quadratic running time. There are some heuristics to improve the running time of computing central vertices if connected components (which is the only quadratic factor in our algorithm and gence the bottleneck) including pruned BFS. However, as far as I know, this is the best achievable asymptotic running time.