silverfish's blog

By silverfish, history, 3 months ago, In English

MDST

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, 2*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, 2*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.

Older version

Above I give an explanation to why this solution works, but it relies on the fact : 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 which I didn't prove.

I have worked out a proof on paper for why this is true, but I'm not sure how to write it down formally here so I will not try to do so. I recommend you try to prove it yourself, if you are struggling write a message to me and I will try to help with what I can.

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by silverfish (previous revision, new revision, compare).

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey!! I am struggling with this problem too..

what I did in my solution is, I calculated the diameter, for every possible root. (Where I did BFS(u) for every node u,then from the fartherest node from u, suppose v, I conducted DFS(v) and then, the fartherest node from v is the diameter considering v as root. In this way I calculated every possible diameter. Then I have chosen the minimum of those diameters. But it was getting WA. Donno why.. can you give me some example for which cases it is getting WA. my code