Find cheapest cycle in an undirected weighted graph

0
votes

I'm stuck on searching an algorithm to find the cheapest cycle in a weighted undirected graph in O(n^2). The cycle does not have to visit every vertex in the graph (i.e. I'm not looking for a Hamiltonian cycle).

Can someone help me finding a strategy?

an example of weighted undirected graph:

enter image description here

1
algorithmgraphgraph-algorithmcycle
Considering the list of all cycles may be longer than O(n^2), the answer is no, we can't help you do that. - user2357112 supports Monica
Your example output is missing cycles. Can you give a precise description of what you want to achieve, or fix your example output if you got the description right the first time? - user2357112 supports Monica
this problem would help me in finding the cheapest tour in weighted graph. A tour is a loop in the cycle, so I have to traverse all nodes to find all cycles and output the one with the minimum weight. - geek4079
@user2357112 I updated the outputs, can you understand it now? - geek4079
If you want to find the cheapest cycle, that's much, much easier than finding all of them. If you want to find the cheapest Hamiltonian cycle, you're still out of luck. - user2357112 supports Monica

1 Answers

3
votes

I'm not sure where the O(n^2) time bound came from. The obvious O(n (m + n log n))-time algorithm is, for each vertex, to compute a shortest-path tree from that vertex and then consider the fundamental cycle made by a non-tree edge and some tree edges.