graph - How to find Minimum Directed Cycle (minimum total weight)?

10
votes

Here is an excise:

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.

Here is my algorithm.

I do a DFS. Each time when I find a back edge, I know I've got a directed cycle.

Then I will temporarily go backwards along the parent array (until I travel through all vertices in the cycle) and calculate the total weights.

Then I compare the total weight of this cycle with min. min always takes the minimum total weights. After the DFS finishes, our minimum directed cycle is also found.

Ok, then about the time complexity.

To be honest, I don't know the time complexity of my algorithm.

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.

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

Can anyone help me with:

  1. Is my algorithm correct?
  2. What is the time complexity if my algorithm is correct?
  3. Is there any better algorithm for this problem?
4
algorithmdata-structuresgraphshortest-path
It's not clear what you're asking for help with. Are you asking for help determining your time complexity? - Keeblebrox
Ok, I edited my question - Jackson Tale
Your algorithm is incomplete. What do you do if you encounter a vertex which you have already seen? - n. 1.8e9-where's-my-share m.

4 Answers

25
votes

You can use Floyd-Warshall algorithm here.

The Floyd-Warshall algorithm finds shortest path between all pairs of vertices.

The algorithm is then very simple, go over all pairs (u,v), and find the pair that minimized dist(u,v)+dist(v,u), since this pair indicates on a cycle from u to u with weight dist(u,v)+dist(v,u). If the graph also allows self-loops (an edge (u,u)) , you will also need to check them alone, because those cycles (and only them) were not checked by the algorithm.

pseudo code:

run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

path(u,v) + path(v,u) is actually the path found from u to v and then from v to u, which is a cycle.

The algorithm run time is O(n^3), since floyd-warshall is the bottle neck, since the loop takes O(n^2) time.

I think correctness in here is trivial, but let me know if you disagree with me and I'll try to explain it better.

5
votes

Is my algorithm correct?

No. Let me give a counter example. Imagine you start DFS from u, there are two paths p1 and p2 from u to v and 1 path p3 from v back to u, p1 is shorter than p2.

Assume you start by taking the p2 path to v, and walk back to u by path p3. One cycle found but apparently it's not minimum. Then you continue exploring u by taking the p1 path, but since v is fully explored, the DFS ends without finding the minimum cycle.

2
votes

"For each vertex, it might point back to one of its ancestors and thus forms a cycle"

I think it might point back to any of its ancestors which means N

Also, how are u going to mark vertexes when you came out of its dfs, you may come there again from other vertex and its going to be another cycle. So this is not (n+m) dfs anymore.

  1. So ur algo is incomplete
  2. same here

3. During one dfs, I think the vertex should be either unseen, or check, and for checked u can store the minimum weight for the path to the starting vertex. So if on some other stage u find an edge to that vertex u don't have to search for this path any more. This dfs will find the minimum directed cycle containing first vertex. and it's O(n^2) (O(n+m) if u store the graph as list)

So if to do it from any other vertex its gonna be O(n^3) (O(n*(n+m))

Sorry, for my english and I'm not good at terminology

0
votes

I did a similar kind of thing but i did not use any visited array for dfs (which was needed for my algorithm to work correctly) and hence i realised that my algorithm was of exponential complexity.

Since, you are finding all cycles it is not possible to find all cycles in less than exponential time since there can be 2^(e-v+1) cycles.