Find cycle of shortest length in a directed graph with positive weights

Question

Hi guys,

I was asked this question in an interview but i couldnt come up with any decent solution. So, i told them the naive approach of finding all the cycles then picking the cycle with the least length.

I'm curious to know what is an efficient solution to this problem.

Thanks, Chander

Answer 1

• Perform DFS
• During DFS keep the track of the type of the edge
• Type of edges are Tree Edge, Back Edge, Down Edge and Parent Edge
• Keep track when you get a Back Edge and have another counter for getting length.

See Algorithms in C++ Part5 - Robert Sedgwick for more details

Answer 2

You can easily modify Floyd-Warshall algorithm. (If you're not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms).

Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won't affect algorithm itself, as those zeroes weren't used in computation anyway (since path path[i][j] will never change for k == i or k == j).

In the end, path[i][i] is the length the shortest cycle going through i. Consequently, you need to find min(path[i][i]) for all i. And if you want cycle itself (not only its length), you can do it just like it's usually done with normal paths: by memorizing k during execution of algorithm.

In addition, you can also use Dijkstra's algorithm to find a shortest cycle going through any given node. If you run this modified Dijkstra for each node, you'll get the same result as with Floyd-Warshall. And since each Dijkstra is O(n^2), you'll get the same O(n^3) overall complexity.

Answer 3

What you will have to do is to assign another weight to each node which is always 1. Now run any shortest path algorithm from one node to the same node using these weights. But while considering the intermediate paths, you will have to ignore the paths whose actual weights are negative.