Halym2007's blog

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

can you share your idea?

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

Comments Comments (7)
| Write comment?
»
15 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
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is your time complexity?

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

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

      → Reply
      • »
        »
        »
        »
        15 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
        • »
          »
          »
          »
          »
          15 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
  • »
    »
    15 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