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

Question

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.

Sands

Answer 1

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.

Fictional

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. – Sackcloth

@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. – Fictional

Thanks..i used the modified version of Dijkstra and it worked – Sands

I think you can do this in O(n^2) times. With 2 dijkstra runs, and two nested for loops will do that. – Artist

Could you make this work for undirected graphs as well? – Jailer

Answer 2

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)

Mismanage

You first set path[s][s] to 0, then in if you have ... or path[s][s] == 0, so keep changing things, even if it's longer??? Typo? – Lamoureux

Answer 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

Schleswig

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. – Fictional

Answer 4

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.

Sackcloth

Answer 5

Below is a simple modification of Floyd - Warshell algorithm.

V = 4
INF = 999999

def minimumCycleLength(graph): 
    dist =  [[0]*V for i in range(V)]
    for i in range(V):
            for j in range(V):
                dist[i][j] = graph[i][j];
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
    length = INF
    for i in range(V):
        for j in range(V):
            length = min(length,dist[i][j]) 
    return length

graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length

Artificial