luciocf's blog

By luciocf, 5 years ago, In English

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?

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          True. I was mistaken.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We need to build not MST, but shortest path tree (we can do it with Dijkstra).

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              From arbitrary vertex in component.

              shortest path TREE (not DAG).

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                And why is this solution supposed to work, sir?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If you mean to build shortest path tree from each vertex, it won`t fit the time limit.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              From one arbitrary vertex.

              It is O(mlogn)

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            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(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          What you said is true but how do you find the shortest path from S to V without using the edge (S,V) ?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But M = 1e5 and tl is only 1 second

»
5 years ago, # |
Rev. 5   Vote: I like it -13 Vote: I do not like it

deleted

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What about the complexity, is it O(V+E) as in a standard BFS?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 4   Vote: I like it -12 Vote: I do not like it

      too

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        I don't see why this is V+E, since we need to start a BFS from every vertex.