[MDST](https://www.spoj.com/problems/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, 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.↵
↵
<spoiler summary="Older version">↵
↵
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:).↵
(Turns out I made a bug in my code)↵
↵
</spoiler>↵
↵
↵
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.↵
↵
↵
↵
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.↵
↵
<spoiler summary="Older version">↵
↵
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:).↵
(Turns out I made a bug in my code)↵
↵
</spoiler>↵
↵
↵
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.↵
↵
↵
↵
