Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

How to Solve This Graph Theory Problem ?

Revision en2, by fakeac, 2017-04-21 13:54:24

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.

History

Revisions

Rev. Lang. By When Δ Comment
en2 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 fakeac 2017-04-21 13:53:27 776 Initial revision (published)