Minimum Weight Cycles with Floyd-Warshall Algorithm

3
votes

"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?

1
algorithmgraphfloyd-warshall
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 :) - j_random_hacker
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. - G. Bach
@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 - Niklas B.
@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. - G. Bach
@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...) - j_random_hacker

1 Answers

2
votes

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.