Hi guys,
I have done some thinking about how to solve 2nd best Minimum Spanning Tree. I want to hear your suggestions on if its correct and how you would solve it. Thanks.
Let G = (V,E) be a graph. Lets assume we know how to solve the MST using Kruskal as that is trivial. At each step of Kruskal, consider an edge e=<a,b>.
If e does not cause a cycle then it is in MST Otherwise It can cause a cycle. Now consider all edges in such a cycle and take the biggest edge in the cycle e1.
Claim : If we maintain the value (e-e1) and minimize it over all cases where adding an edge will introduce a cycle then we would have the 2nd best MST by simply replacing e1 with e.
Is this true ? How would you solve this problem ?
Thanks.
Any ideas???
I have problems understanding your claim.
Can you write it in psuedo code or elaborate a bit more?
Thanks, Let me try to elaborate on it more.
I will try to say little about the general reasoning on Kruskal and then use that as a spring board for the claim.
Each Iteration in Kruskals MST algorithm tries to add an edge from a priority queue to another set of edges that "must" be in the MST.
Now consider such an iteration and let E=(a,b) be an edge from the priority queue. When we try to add E to the set of "must" spanning tree two cases come out
Case 1: No cycles formed
Case 2: A cycle is will be formed. So we don't add E. Consider such a cycle that "could have been formed" and let us denote it by e1-e2-e3-...-E. Where e1 = (b,x) and E=(a,b).
my claim.
What if we can calculate the difference of the weight on E and some other weight on one of the edges say the one with the largest weight.
E.weight > ei.weight
d = E.weight — ei.weight;
If we minimize this value d over all iterations of Kruskals algorithm and then add
d — ei.weight to the final value of the best MST, this will give us the second best MST.
Hope its clearer now.
Ok now I think I know what you mean.
Your method is almost equivalent to a O(V2) algorithm I know.
Except that there's a tiny issue with your idea.
You need to minimize d over all edges, rather than iterations of Kruskals only. Fix that, and I think your idea should be correct :)
1) Build MST
2) Iterate over the edge(u, v). If this edge is in MST -> continue; else
find lca = LCA(u, v);
now u need to find maxEdge on path lca->u and maxEdge on path lca->v, it can be done using binary "ascent?".
define x = maxEdge. we update answer by value (InitMST + W(u, v) — x).
I think you mean maximum edge since you want to minimize the quantity W(u,v) — x.
yeah, thx.
It turns out that my intuition was correct and that the only part missing for me is using LCA algorithm to find maximum distance on cycle.
For more info see http://codeforces.net/blog/entry/9570
You don't really need LCA for this one. I don't have the energy to explain it right now.
However, consider doing a simple Prim/Kruskal algorithm first to find out an arbitrary MST,
then do the minimization through all edges (not on the MST) afterwards.
When you have the MST already, you can preprocess by starting from an arbitrary vertex and record on each vertex, the longest edge it has seen so far. This way, the query takes O(1) for each edge you check.
you can still do stuff with dsu to find that
Can you please elaborate a little on it.
Ok now you have the Mst,
let's say that the Mst's edges are in the array e[N]
and we know that e[i].w <= e[i+1].w
we have m — n + 1 queries which are like what is the longest edge's weight from u to v in the mst (the queries are the edges which are not in mst)
now let's say that at first all vertices are in their own sets and we will add edges one by one and we will merge the two sets which are located at the endpoint of the edges (move the smaller one to the bigger one) and we will check the queries of the smaller one to see if there is any queries that goes from the smaller to the bigger one the answer of the query is this edge's weight
the complexity is O(qlgn + nlgn)