Find cycle of shortest length in a directed graph

问题:

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.

回答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.

回答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)

回答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

回答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.

回答5:

We can also use branch and bound algorithm for travelling salesman problem, as your question matches with TSP. http://lcm.csa.iisc.ernet.in/dsa/node187.html

回答6:

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