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

I was asked this question in an interview, but I couldn't 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.

-

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.

-
This is not as per the requirements. In these algorithms the shortest means the least weighted and not the least length. e.g. if there are two cycles like 1,2,3 and then 100,500; then cycle 1 will be chosen, but what is required is cycle 2 as it has shortest length. Correct me if I am wrong. – Manoj R Oct 12 '10 at 9:59
@Manoj Second problem is a subset of first. Just assign weight 1 to each edge and you'll receive path with smallest number of edges. The real problem (although small one) is that neither Dijkstra, nor Floyd-Warshal find a shortest path from node back to itself. You'll have to tweak them a little. – Nikita Rybak Oct 12 '10 at 10:52
Thanks..i used the modified version of Dijkstra and it worked – Chander Shivdasani Oct 12 '10 at 13:14
I think you can do this in O(n^2) times. With 2 dijkstra runs, and two nested for loops will do that. – user482594 Feb 8 '12 at 5:53
Could you make this work for undirected graphs as well? – Thomas Ahle May 19 '14 at 20:53

The pseudo code is a simple modification of Dijkstra's algorithm.

``````for all u in V:
for all v in V:
path[u][v] = infinity

for all s in V:
path[s][s] = 0
H = makequeue (V) .. using pathvalues in path[s] array as keys
while H is not empty:
u = deletemin(H)
for all edges (u,v) in E:
if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
path[s][v] = path[s][u] + l(u,v)
decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
if path[v][v] < lengthMinCycle & path[v][v] != 0 :
lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
print(“The graph is acyclic.”)

else:
print(“Length of minimum cycle is ”, lengthMinCycle)
``````

Time Complexity: O(|V|^3)

-
• 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

-
Nice try, but this has exponential complexity at best. I suspect, Robert Sedgwick is solving some more general and complex problem in his book, as this one is much easier. – Nikita Rybak Oct 12 '10 at 7:52

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.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}