My solution is O(N^4).

Edited by author 06.08.2009 08:42

Edited by author 06.08.2009 08:42

You should use Dijkstra algorithm for every vertex. In algorithm you should find two different best ways from current vertex V to any other A. The summary length of this two ways is the length of the shortest cycle with vertexes A and V.