Databases
StackOverflow2013
Postsdbo
POgraph - How to find Minimum Directed Cycle (minimum total weight)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJackson Tale
    1. USJackson Tale
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. USK Z
      1. VTFavorite
    1. COIt's not clear what you're asking for help with. Are you asking for help determining your time complexity?
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. USKeeblebrox
    2. COOk, I edited my question
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. USJackson Tale
    3. COYour algorithm is incomplete. What do you do if you encounter a vertex which you have already seen?
      singulars
      1. POgraph - How to find Minimum Directed Cycle (minimum total weight)?
      1. USn.m.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload