0
$\begingroup$

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?

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.