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

Question

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?

Solution 1

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.

Solution 2

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.

Solution 3

"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

Comments

[Jackson Tale]

Thanks. I believe your suggestion is correct, although I am still try to understand it. I understand Floyd algorithm and it sure finds all pairs shortest path. So in the end, we get a matrix listing the shortest weights between all pairs. And then to find out which cycle has the minimum total weights, we just can the matrix again. If matrix[i][j] != MAX_INT and matrix[i][j] != MAX_INT, then i and j has cycle and the total = matrix[i][j]+matrix[j][i], then we can find the minimum one, am I right? To record the structure of the cycle, we have to use another parent matrix, right?

[amit]

@JacksonTale: (1) You are correct, also note my edit: this solution does not take care for self loops (edges like (u,u)), so if these are allowed in the graph - it will have to be checked in addition (it is easy). Note that once you found which pair is the required, you can use dijkstra or BF from u to find the path u->...->v, and then again from v to find v->...->u, without changing the total complexity of the algorithm, so getting the actual path is not an issue for this problem.

[alestanis]

For more readability, you should use the code format by surrounding your variable names with backticks like `this`

[shuais]

Thanks for your advice. Updated.

[tiwo]

What's wrong with dist(u,u)? If that doesn't give the length of the shortest cycle u→...→u (including self loops), are be talking of different Floyd-Marshals?