title: How to find the shortest directed cycle in a directed graph?
body: <p>From <a href="https://algs4.cs.princeton.edu/42digraph/" rel="nofollow noreferrer">https://algs4.cs.princeton.edu/42digraph/</a></p>
  
  <blockquote>
    <ol start="40">
    <li><strong>Shortest directed cycle.</strong> Given a digraph, design an algorithm to find a directed cycle with the minimum number of edges (or report that
    the graph is acyclic). The running time of your algorithm should be
    proportional to E V in the worst case.</li>
    </ol>
  </blockquote>
  
  <p>The solution is found here: <a href="https://algs4.cs.princeton.edu/42digraph/ShortestDirectedCycle.java.html" rel="nofollow noreferrer">https://algs4.cs.princeton.edu/42digraph/ShortestDirectedCycle.java.html</a></p>
  
  <pre><code>public ShortestDirectedCycle(Digraph G) {
      Digraph R = G.reverse();
      length = G.V() + 1;
      for (int v = 0; v &lt; G.V(); v++) {
          BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
          for (int w : G.adj(v)) {
              if (bfs.hasPathTo(w) &amp;&amp; (bfs.distTo(w) + 1) &lt; length) {
                  length = bfs.distTo(w) + 1;
                  cycle = new Stack&lt;Integer&gt;();
                  for (int x : bfs.pathTo(w))
                      cycle.push(x);
                  cycle.push(v);
              }
          }
      }
  }
  </code></pre>
  
  <p>The solution makes sense to me, except for the first line <code>G.reverse()</code>. Why? Does it have anything to do with Topological sort?</p>
  
  <p>There are quite a few questions on SO regarding finding all cycles in a Digraph, but I'm assuming there's a better way than finding all cycles and comparing their lengths. There are some questions regarding finding the shortest directed cycle, but none has an acceptable answer.</p>
  
  <p><a href="https://stackoverflow.com/q/5700148/839733">How can I find the shortest cycle in a Directed, Weighted Graph?</a></p>
  
  <p><a href="https://stackoverflow.com/q/30614896/839733">Find the Shortest Cycle in Graph</a></p>
  
  <p><a href="https://stackoverflow.com/q/47795348/839733">Finding shortest cycles in directed or undirected graph</a> (this one is for undirected graph)</p>
  
  <p>I also found a <a href="https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf" rel="nofollow noreferrer">paper</a> that uses BFS, but the pseudocode presented can't be used to reconstruct the path, only to find the length of the shortest cycle.</p>