I'm trying to find an algorithm for computing a minimum diameter spanning tree of a graph or just the length of the diameter of a minimum diameter spanning tree. There is a problem on SPOJ related with this:(http://www.spoj.com/problems/MDST) . I wonder if somebody could help me to find some information about this.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
there are 1000 vertexes , but my way is n^3 ,so let's wait for some cows to reply
Could you tell me your n^3 solution!
http://www.spoj.com/problems/PT07C/ i think this problem is a similar problem , but there are only 200 nodes
It's solvable in O(nm) [submit_id = 9109775, running_time = 0.77].
For each vertex v do bfs(v), so you have all distances d[i, j].
After it brute force center of MDST (it's a vertex or an edge).
How can we know the constraint on t to be sure that our solution can pass tests? I didn't find it in the problem statement. Generally, I have this problem with most of the SPOJ's problems.
But when the center is on an edge it's not so easy!! is it?? Could you explain more about this?? Thanks in advance!
UPD: I mean that is not so easy when the center is on an edge in weighted graphs
You can split each edge by a fake vertex.
UPD. Oh, this is for unweighted graph.
I'm looking for an algorithm for weighted graphs!!
I think this algorithm can be converted for weighted graph :
For each vertex as a root find it's shortest path tree and calculate it's diameter.
Could someone confirm this?
Wouldn't it take O(n^3) time to find distances between all pairs of vertices? I don't quite understand this part of the implementation.
O(nm) = O(n3), because m = O(n2) it depends on how many edges in the graph.
Not for sparse graphs.
I fixed my code, had a stupid mistake. If anyone is struggling with the problem I wrote a blog explaining the solution:)).
"After it brute force center of MDST (it's a vertex or an edge)." Could not understand, why would we need to find the center of the diameter? Why it is not enough, if we do bfs for every node, and count the minimum diameter for every possible root?
Well I tried this approach, and got wa after 4th test case.. :/
Can anybody give a proof why calculating only shortest path tree for all nodes as a root gives us a correct output? Their are many other tree configurations possible,which might give us the shortest diameter.
EDIT:In context to THIS Thank you.
Are you sure calculating shortest path tree for every vertex logic is correct ? I implimented it for this problem ->http://www.spoj.com/problems/PT07C/ but got WA . http://ideone.com/YDRLYF
"After it brute force center of MDST (it's a vertex or an edge)."
You should check not only vertices, but also pairs of adjacent vertices.
Look at the graph 1-2-3-4. The center of a graph is an edge between vertices 2 and 3.
Bruteforce all edges. Do not run bfs for each edge. Calculate distance via
dist[(edge (a, b))][i] = min(dist[a][i], dist[b][i]);In case anyone wants to learn about Min. Diameter Spanning Tree (MDST) on a weighted graph, here's a very good resource: Explanation of problem C in pdf.
Here's a problem that requires this idea: 266D - BerDonalds