There is a spoj problem where you need to find the diameter of the MDST for a given graph. The graph is undirected, connected and unweighted. There are up to 1000 nodes, but no bound is given on the number of edges. (the solution I found online looped through all the edges and than all the nodes, and got AC. I think its thus safe to assume the number of edges is O(n))

From what I've read online here's the logic of the solution:

1. find the shortest distance dist[u][v] from each node to each other node (done in O(n^2), with bfs from each node)

2. brute force the center of the MDST

   1. If the center of the MDST is a node v, I find the node u such that dist[v][u] is maximal. -> The diameter if v is center will be 2*dist[v][u] I keep a variable mdst as the minimum diameter I have found so far.

   mdst = INF;
   for(v = 0 to N){
      mx = 0
      for(u = 0 to N) 
          mx = max(mx, dist[v][u])
      mdst = min(mdst, mx)
   }
   

   2. If the center of the MDST is an edge e = (u, v) I find the node x such that min(dist[u][x], dist[v][x]) is maximal. -> the diameter if e is the center will be 2*min(dist[u][x], dist[v][x]) + 1

   for((u, v) : edges){
      mx = 0
      for(x = 0 to N) 
          mx = max(mx, min(dist[u][x], dist[v][x]))
      mdst = min(mdst, mx)
   }
   

In either of the above cases, if the chosen node/edge is not the center of the MDST, the resulting diameter I find will be strictly greater than that of the actual MDST. On the other hand if the chosen node/edge is the center of the MDST, I should find the correct diameter.

But this doesn't work (at least my implementation of this doesn't work). Thanks for anyone who read through this whole thing, and even more thanks to anyone who can tell me where I messed up and end my suffering with this problem:).