I was thinking about this problem for quite a while but couldn't solve it. The statement is the following:
Given an undirected and weighted simple graph with $$$N$$$ vertices and $$$M$$$ edges, find the cost (sum of weights in edges) of its shortest cycle, that is, the one with least cost. Repeated edges are not allowed in the cycle.
Note: It is assumed the graph has at least one cycle.
Constraints:
$$$1 \leq N \leq 10^4$$$, $$$1 \leq M \leq 10^5$$$
$$$0 \leq W_i \leq 100$$$, where $$$W_i$$$ is the weight of the ith edge.
The problem can be found here: https://dunjudge.me/analysis/problems/697/. Can anyone help me solve it?
My idea:
We will solve independently for each component. Let’s find MST. Now every edge which is not included in MST saycet cycle. Iterate over all such edges and relax answer with length of this cycle. It can be done with binary lifting.
i also thought of the same idea, but could not prove it, have you submitted this idea, if its correct can you enlighten with some proof?!
No, I haven’t submitted this. Let’s say answer contains more than one edge which is not included in MST. Then we can select one of this edges and replace it by path which it closes.
It isn't necessary that the MST distance will be less than the weight of the replaced edge. The only guarantee is that max weight on the path is <= non-MST edge.
True. I was mistaken.
We need to build not MST, but shortest path tree (we can do it with Dijkstra).
From which vertex do you want to build shortest path tree? And this is not neceserally a tree, all we have that it will be a DAG, so i don't see how you would apply binary lifting here.
From arbitrary vertex in component.
shortest path TREE (not DAG).
And why is this solution supposed to work, sir?
If you mean to build shortest path tree from each vertex, it won`t fit the time limit.
From one arbitrary vertex.
It is O(mlogn)
Are you sure that works? If I understood you correctly, I think your solution fails in this case (if you choose vertex 1 as root):
4 6
1 2 1
1 3 1
1 4 1
2 3 0
3 4 0
2 4 0
The shortest cycle is 2-3-4 with length 0, but the SP Tree found could be 1-2 1-3 1-4.
Shortest path tree is: 1-2 2-3 3-4
Sorry for repetition of the old joke about _overrated_ , but in fact it is not a joke((( He writes comments before thinking on them to often(
Man you ......
I think this doesn't work for the following case : N = 8, M = 9
1-2 1
2-3 1
4-5 1
5-6 1
6-7 1
7-8 1
1-7 2
1-8 2
Here, the MST is the chain formed by the first 7 edges but the shortest cycle is 1-7-8-1
My idea:
For each edge in the graph, run Minimum Cost Maximum Flow algorithm where the source is the first end of the edge and the sink is the second end of the edge. The answer will be the minimum of all MCMF of each edge.
But I don't know if it will pass the TL or no.
That's a ban, sir.
My solution overall is propably pretty similar to Pepegas one. We can assume for each edge that it is a part of the cycle we are looking for. Then for each edge we can bin-search a value from 0 to N*M, then subtract this value from the edges cost and run Bellman-Ford or Floyd-Warshall to check whether we have a negative cycle or not. Via bin-search we want to find the very last moment before there is a negative cycle. We take minimum over all edges. The complexity is O(N*M^2*log(NM)), i do not know if we can do faster using this approach.
My idea:
For each edge(u,v,w) : Delete it and run Dijkstra from one of its endpoints and let T be the distance between u and v, the answer is the minimum over all T+w.
Since we are performing M dijkstras, the complexity is O(M^2 log N)
You can improve that to O(N * MlogM) if you run N Dijkstras, with sources being vertices from 1 to N and finding the minimum weight cycle starting from one of them.
I didn't quite get you. How do you ensure that the edge you're checking isn't already a part of the shortest path?
I did not notice that W could be equal to 0 and my proof relies on that, but I think that's not a big problem because we can merge all vertices connected by an edge of weight 0 into one big vertex.
So, if I understood correctly your concern is: if S is the source vertex, and we are currently on vertex V in the Dijkstra algorithm, how can we ensure that the edge (S, V) is not part of the shorthest path from S to V.
Well, that is only possible if the shortest path from S to V is the edge (S, V) and we can easily check that if we also keep from which vertex we came from in the shortest path to V.
What you said is true but how do you find the shortest path from S to V without using the edge (S,V) ?
You are right. I forgot about that, but I think we can work around it by also finding the second shortest path to every vertex, since the edge (S, V) is included in only one path from S to V.
But M = 1e5 and tl is only 1 second
deleted
What about the complexity, is it O(V+E) as in a standard BFS?
too
Sorry for asking another question. Does the algorithm work in an undirected graph? In the link you showed it says that it works in a directed graph.
I don't see why this is V+E, since we need to start a BFS from every vertex.
Neither do I ...