sahil070197's blog

Cycle with minimum weights
By sahil070197, history, 7 years ago, In English

I need help in finding cycle with minimum weights in an undirected graph.Basically i am looking for an efficient approach , of lower time complexity than that of applying dijkstra after removing every edge and adding that back, it has time complexity of O(E^2logV). So something better than this..

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

Comments Comments (7)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

If you use Floyd-Warshall to find the minimum cycle,the complexity is O(v^3).Maybe it can run faster in a graph that the number of edges is a lot larger than the number of vertices.And this one,as well as the one you mentioned above,is the most efficient way to find the minimum cycle in a graph.

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

    Why so many downvotes?

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

      From what I understand, the same edge can't be used twice as otherwise the problem would be as simple as double the smallest edge. Floyd-Warshall would use the same edge twice so it wouldn't be correct.

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

        I think he meant not just simply do Floyd-Warshall. And indeed it can find the minimum cycle without using the same edge twice.

        The main idea is before we try to update dist(u, v) with vertex w, we know that dist(u, v) doesn't contain vertex w, so we can update ans to min(ans, dist(u, v) + edge(u, w) + edge(w, v)).

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

        Maybe you misunderstand what I mean,it's obviously wrong that we use the minimal distance from i to i to update the answer.Instead,when we do FLoyd,before we update dis[i][j] by dis[i][k]+dis[k][j]，we can update our answer by dis[i][k]+dis[k][j]+dis[j][i].And it's proved to be correct.

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

    Thanks.. :)

    → Reply