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

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.

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)