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