This problem appeared in one of my university assignments, but I only know of one algorithm which is to find Shortest Distance from each node node to every other node using Dijkstra's Algorithm and take the maximum of all distances found in each iteration. This is going to take time = O(V(E+V)log(V)) which is too large for the given data set.

I don't understand what does the approach — "Instead, randomly select pairs of vertices and evaluate minimum weight path (also referred to as shortest path) between them", mentioned in the 4th question mean. Please help.!Here is the problem statement. I need help for the 4th problem.