We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. For
an undirected graph
G of unknown girth
k, our algorithm returns with high probability a cycle of length at most 2
k for even
k and 2
k + 2 for odd
k, in time

Thus, in general, it yields a

approximation. We study also the problem of finding a simple cycle of minimum total weight in an undirected graph with nonnegative
edge weights. We present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle in an undirected
graph with nonnegative integer edge weights in the range { 1,2,...,
M}. This algorithm runs in time