3

"Let G be a directed weighted graph with no negative cycles. Design an algorithm to find a minimum weight cycle in G that runs with a time complexity of O(|V|^3)."

The above is a question I have been working on as part of my coursework. When I first read it, I immediately thought that the Floyd-Warshall algorithm would solve this problem - mainly because F-W runs in O(|V|^3) time and it works for both positive and negative weighted graphs with no negative cycles. However, I soon remembered that F-W is designed to find the shortest path of a graph, not a minimum weight cycle.

Am I on the right track with this question? Would it be possible to modify the Floyd-Warshall algorithm to find a minimum weight cycle in a graph?

Improve this question
8
  • 1
    Yes, you're on the right track. A minimum-weight cycle containing a vertex v consists of a minimum-weight _____ beginning at _____, followed by a[n] _____. Fill in the blanks :) Commented Mar 30, 2014 at 0:35
  • I have no idea what the blanks above are supposed to be, but a cycle is a (nontrivial) path from a vertex to itself. You'll just have to adjust the initial settings of FW to get what you want. Commented Mar 30, 2014 at 0:42
  • @G.Bach I think hacker meant that you can contruct the minimum cycle in O(n^3) if you have solved all-pairs shortest paths first. It's much harder if we want to find a simple cycle without repeated nodes Commented Mar 30, 2014 at 0:48
  • @NiklasB. I think it might be enough split every vertex in two, connect them with a zero weight edge and adjust all edges in the way it's usually done for this operation. Then we run Floyd-Warshall, looking for the shortest path from v_o to v_i where v ranges over all vertices. Since I don't remember whether Floyd-Warshall may give you nonsimple paths, once we have a path we can easily strip it of all (zero weight) cycles in it in linear time. Commented Mar 30, 2014 at 1:23
  • @G.Bach: That will work for a directed graph like this one, provided you make the added edges from v_i to v_o in each case. (But please try not to give a complete answer to a homework question...) Commented Mar 30, 2014 at 1:36

1 Answer 1

Reset to default
2

I think you are pretty close. Once you do FW loop in O(|V|^3), you have the weight of a shortest path between each pair of vertices, let's call it D(i, j). Now the solution to our main problem is as follows: Brute force for the vertex which is gonna be in a loop, say it's X. Also brute force on Y, which is gonna be the last vertex in the cycle, before X itself. The weight of this cycle is obviously D(X, Y) + W(Y, X). Then you just choose the one with the smallest value. It's obviously a correct answer, because: (1) All these values of D(X,Y)+D(Y,X) represent the weight of some(maybe non-simple) cycle; (2) If the optimal cycle is some a->...->b->a, then we consider it when X=a, Y=b;

To reconstruct the answer, first you need to keep track of which X, Y gave us the optimal result. Once we have this X and Y, the only thing remaining is to find the shortest path from X to Y, which can be done in various ways.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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