4

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.

Dominique Fortin
  • 2,212
  • 15
  • 20
Abhijit Sarkar
  • 21,927
  • 20
  • 110
  • 219
  • 2
    This question is actually asked at Coursera Algorithms Part 2 course. Considering that the course and your link are from the same author, this answer is correct. I see the main idea of this solution: if you have some neighbor in a straight graph and you can somehow reach it in a reversed graph, it is a cycle. I think the most similar algorithm is Kosaraju which reverses a graph to find strongly connected components. – vortexwolf Mar 13 '19 at 07:52
  • 1
    @vorrtex _"This question is actually asked at Coursera Algorithms Part 2 course. Considering that the course and your link are from the same author..."_ is that somehow relevant? how does it matter where else this question is asked, and by who? – Abhijit Sarkar Mar 13 '19 at 09:53

1 Answers1

4

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.

ruakh
  • 175,680
  • 26
  • 273
  • 307
  • Why not just check for `bfs.hasPathTo(v)` for every `v`? – Abhijit Sarkar Jun 24 '18 at 03:50
  • @AbhijitSarkar: I imagine that `bfs.hasPathTo(v)`, `bfs.distTo(v)`, and `bsf.pathTo(v)` would always return `true`, `0`, and the empty path (respectively). Of course, it could be changed to ignore the empty path; the code that you've posted only makes sense, IMHO, if `BreadthFirstDirectedPaths` is also used for other things. – ruakh Jun 24 '18 at 04:51