Alex Rivera | Logout

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

Asked 2010-10-12T04:10:49.020
24

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.

algorithm graph dijkstra
Edit
Report

1 Answer

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

answered 2010-10-12T05:34:50.210

Your Answer