# Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $O(VE^2)$ times, and Bellman Ford runs $O(VE)$ time so we are looking at a modification that runs $O(E)$

My approach is first make a directed graph by doubling the edges in both directions, then run Bellman Ford to come up with the shortest path, then compute the strongly connected components in this graph. After you have a tree of strongly connected components, calculate the weights around the perimeter of the SCC and then compare the weights. But I'm not sure how you could calculate SCC using Bellman Ford and this algorithm is going to take too long.

Does anyone see an obvious solution?

Some hints for you, so you can solve your own exercise:

• If the graph has a negative-weight cycle, what is the proper answer? Can you detect this situation?

• If the minimum-weight cycle has positive weight (strictly greater than zero), how could you find it? If you knew the distance between every pair of vertices, could you use that to help you find the minimum-weight cycle in this case? Does that suggest an algorithm that could handle this case?

• If the minimum-weight cycle has zero weight, can you detect this fact? What could you do in this situation?