pas.andrei's blog

Minimum-cost cycle
By pas.andrei, history, 8 years ago, In English

I am given a undirected (multi-)graph with N vertices and M edges. I have to find a cycle of minimum cost in this graph and then print the vertices in their traversal order. Also, I can't use the same edge twice.

In the following example the numbers on the first line represent N and M. On each of the following M lines there are 3 numbers: x, y and c, meaning that there is an undirected road between x and y with cost c.

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Answer:
1 3 5 2 1
  • Vote: I like it
  • +10
  • Vote: I do not like it

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

Create an MST from the given graph. Keep track of the unused edges. For every unused edge, add this edge in the tree. You will get a cycle in the tree. Determine the cost of the cycle and update the result. You've to use sparse table data structure to pass the time limit. Hope it helps :)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it
    • 6 7
    • 1 2 1
    • 2 3 1
    • 3 4 1
    • 4 5 1
    • 5 6 1
    • 1 5 2
    • 1 6 2

    MST is (1, 2), (2, 3), (3, 4), (4, 5), (5, 6). Minimum cycle is {1, 5, 6} with weight 5.

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

      Thanks for the input. It's my bad that I didn't think more. Can you please give me an idea how to solve this problem when N = 100000?

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

    I think that if I construct a shortest path tree and then try to connect any 2 nodes (different from root) with an used edge would create a cycle, and out of all these cycles I choose the one with minimum cost. The problem I have now is how to keep track of used edges since I have a multigraph.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So, can anyone explain how you solve this for N <= 100? I can't solve it :|. This is the problem, btw.

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

    Iterate over all edges. For each one remove that edge from the graph then run Dijikstra between end points of that edge.

    Marking with a boolean array will pass for N <= 100

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

      Ohhh, this makes sense. Now I feel stupid. Thank you!

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      This approach actually gives TLE on that particular problem (I tried it myself), since it runs in O(E^2) time, which is about 10^10. You can make it O(N^3) this way: for every vertex run Dijkstra and build a shortest path tree. Then for every edge (u, v) which is not in tree and lca(u, v) = root try plugging it into the tree and compute length of created cycle. After that choose overall minimum. Dijkstra should be O(N^2+M) of course, since graph can be dense.

      → Reply