How to Solve This Graph Theory Problem ?
Difference between en1 and en2, changed 4 character(s)
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+vV)log(vV)) 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.↵
![ ](http://codeforces.me/predownloaded/4b/b9/4bb9fb039611716e09ac78b2c007b74976f4a69e.png)↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English fakeac 2017-04-21 13:54:24 4 Tiny change: 'e = O(V(E+v)log(v)) which i' -> 'e = O(V(E+V)log(V)) which i'
en1 English fakeac 2017-04-21 13:53:27 776 Initial revision (published)