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?

  • 3
    $\begingroup$ 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. $\endgroup$ – joriki Mar 3 '12 at 7:23
  • $\begingroup$ 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. $\endgroup$ – joriki Mar 3 '12 at 10:26

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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