CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorybreadth-first-search
Abhijit Sarkar
Abhijit Sarkar

Reputation: 24618

How to find the shortest directed cycle in a directed graph?

From https://algs4.cs.princeton.edu/42digraph/

  1. Shortest directed cycle. Given a digraph, design an algorithm to find a directed cycle with the minimum number of edges (or report that the graph is acyclic). The running time of your algorithm should be proportional to E V in the worst case.

The solution is found here: https://algs4.cs.princeton.edu/42digraph/ShortestDirectedCycle.java.html

public ShortestDirectedCycle(Digraph G) {
    Digraph R = G.reverse();
    length = G.V() + 1;
    for (int v = 0; v < G.V(); v++) {
        BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
        for (int w : G.adj(v)) {
            if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
                length = bfs.distTo(w) + 1;
                cycle = new Stack<Integer>();
                for (int x : bfs.pathTo(w))
                    cycle.push(x);
                cycle.push(v);
            }
        }
    }
}

The solution makes sense to me, except for the first line G.reverse(). Why? Does it have anything to do with Topological sort?

There are quite a few questions on SO regarding finding all cycles in a Digraph, but I'm assuming there's a better way than finding all cycles and comparing their lengths. There are some questions regarding finding the shortest directed cycle, but none has an acceptable answer.

How can I find the shortest cycle in a Directed, Weighted Graph?

Find the Shortest Cycle in Graph

Finding shortest cycles in directed or undirected graph (this one is for undirected graph)

I also found a paper that uses BFS, but the pseudocode presented can't be used to reconstruct the path, only to find the length of the shortest cycle.

Upvotes: 4

Views: 5082

Answers (1)

ruakh
ruakh

Reputation: 183544

G.reverse() is a digraph that's the same as G except that each edge is reversed; so, for example, if G has an edge from v to w, then G.reverse() has an edge from w to v.

Since bfs is taken from G.reverse() and v, bfs.hasPathTo(w) means "whether G has a path from w to v", and bfs.distTo(w) means "the length of G's path from w to v". (If bfs were taken from G instead of G.reverse(), it would detect paths going the other way.)

So the cycle-finding algorithm it's using is: for each edge (v,w) in G, test whether G has a path from w back to v.

Topological sorting is not involved.

Upvotes: 4

Related Questions