Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?
like image 512
Jackson Tale Avatar asked May 04 '12 22:05

Jackson Tale


People also ask

How do you find the minimum cycle on a graph?

The idea is to use shortest path algorithm. We one by one remove every edge from the graph, then we find the shortest path between two corner vertices of it.

How do you find the shortest cycle in a directed graph?

Finding the shortest cycle in a directed unweighted graph: start a breadth-first search from each vertex; as soon as we try to go from the current vertex to an already visited vertex, then it means that we have found the shortest cycle containing the source vertex, and should stop the BFS; from all such cycles (one ...

How do you find the weight of a graph?

This chapter describes the weight of a graph. The weight w(E) of an edge E in a multigraph G is the sum of the degrees of its end vertices; and if G is a pseudograph and E is a loop, then w(E) is defined as twice the degree of its unique end vertex.

What is the weight of a directed graph?

Weighted directed graphs (also known as directed networks) are (simple) directed graphs with weights assigned to their arrows, similarly to weighted graphs (which are also known as undirected networks or weighted networks).


2 Answers

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.

like image 85
shuais Avatar answered Oct 29 '22 01:10

shuais


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.

like image 28
amit Avatar answered Oct 29 '22 00:10

amit