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

algorithm, data-structures, graph, shortest-path

Solution

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.

Problem

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: - Is my algorithm correct? - What is the time complexity if my algorithm is correct? - Is there any better algorithm for this problem?

Original source