Finding shortest cycles in directed or undirected

2019-08-03 03:43发布

问题:

I'm looking for an algorithm to find the shortest cycle in a directed or undirected graph.

For example, for node 3, the algorithm could return:

  • cycle 1 : 3->10->11->7->8->3
  • cycle 2 : 3->10->9->8->3

For these cycles and the shortest is cycle 2, at four vertices.

I did some research and could find the Dijkstra algorithm, DFS, BFS and some others but they always show a path not a cycle.

PS : the arrows are not significant. Thank you for your help.