title: graph - How to find Minimum Directed Cycle (minimum total weight)?
body: <p>Here is an excise:</p>
  
  <blockquote>
    <p>Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n^3) algorithm to find a directed cycle in G of minimum total weight. Partial credit will be given for an O((n^2)*m) algorithm. </p>
  </blockquote>
  
  <hr>
  
  <p>Here is my algorithm.</p>
  
  <p>I do a <code>DFS</code>. Each time when I find a <code>back edge</code>, I know I've got a directed cycle. </p>
  
  <p>Then I will temporarily go backwards along the <code>parent array</code> (until I travel through all vertices in the cycle) and calculate the <code>total weights</code>. </p>
  
  <p>Then I compare the <code>total weight</code> of this cycle with <code>min</code>. <code>min</code> always takes the minimum total weights. After the DFS finishes, our minimum directed cycle is also found.</p>
  
  <hr>
  
  <p>Ok, then about the time complexity.</p>
  
  <p>To be honest, I don't know the time complexity of my algorithm. </p>
  
  <p>For DFS, the traversal takes O(m+n) (if m is the number of edges, and n is the number of vertices). For each vertex, it might point back to one of its ancestors and thus forms a cycle. When a cycle is found, it takes O(n) to summarise the total weights. </p>
  
  <p>So I think the total time is O(m+n*n). But obviously it is wrong, as stated in the excise the optimal time is O(n^3) and the normal time is O(m*n^2).</p>
  
  <hr>
  
  <p>Can anyone help me with:</p>
  
  <ol>
  <li>Is my algorithm correct?</li>
  <li>What is the time complexity if my algorithm is correct?</li>
  <li>Is there any better algorithm for this problem? </li>
  </ol>