Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I want to detect the shortest cycle in a directed graph with positive or negative weights. My idea is to run dfs on every vertex to find cycles by remembering the back edge, then storing all cycles discovered on to a stack. After that I check the cycle with the shortest length in the stack and output it. Does this algorithm work?

share|improve this question
3  
The first hits under "shortest cycle" are this question: stackoverflow.com/questions/3911626/… and this article: en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. Also note that storing the cycles on a stack is wasteful if you just want to find the shortest one in the end; you only have to keep the shortest one you've found so far to do that. –  joriki Mar 3 '12 at 7:23
    
Listing's answer assumes that by "cycle" you mean "simple cycle", i.e. a cycle without repeated vertices. Perhaps you should clarify whether that was the intended meaning. –  joriki Mar 3 '12 at 10:26

1 Answer 1

up vote 1 down vote accepted

Assign every edge weight $-1$. Then the shortest cycle in your digraph is the longest cycle in the unweighted digraph. Therefore computing the answer would yield the result to the np-complete directed hamilton-cycle problem. If $\text{P}\neq\text{NP}$ you can therefore find no polynomial algorithm to compute the shortest cycle. You will therefore not come around finding all cycles in the graph, a discussion on how to do this can be found here.

The algorithm you describe is polynomial as far as i can tell (you essential run $n$ times dfs which is linear in time).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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