Halym2007's blog

how to find shortest cycle in weighted undirected graph?
By Halym2007, history, 12 months ago, In English

can you share your idea?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Dijkstra Algorithm for Each Vertex

Run Dijkstra from each vertex. While doing so, keep track of the shortest path to each other vertex.

When considering a new edge during the algorithm, if the edge leads to a vertex already visited, you have found a cycle. Calculate its length and compare it with the shortest cycle found so far.

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

    what is your time complexity?

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      $$$O(EV\log V)$$$

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

        Is there any way to find with MST(minimum spanning tree)?

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Are you looking for something faster than $$$O(EV)$$$? If yes, that isn't possible with MST. Consider a graph where every edge has the same weight. Now the MST is just any spanning tree and it doesn't give you any extra info. This case can be solved in $$$O(EV)$$$ by replacing dijkstra with bfs since all edges have the same weight, but nothing faster is possible afaik.

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

    thanks

    → Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can also do this in O(V^3) using Floyd

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Given a positive weighted undirected graph, find the minimum weight cycle in it. The idea is to use shortest path algorithm. We one by one remove every edge from the graph, then we find the shortest path between two corner vertices of it. We add an edge back before we process the next edge.Halym2007

→ Reply