2

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

enter image description here

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.

gilleain
  • 621
  • 3
  • 11
  • 24
Kamil
  • 176
  • 2
  • 14
  • Sorry, previous comments were about the smallest *set* of smallest rings, not just the smallest ring. What do you mean by 'always show a path'? – gilleain Dec 13 '17 at 14:39
  • Directed or undirected? There is a difference – DAle Dec 13 '17 at 14:48
  • You probably want to add "non-trivial" circles to your question, since in unidirected graphs you can always have a circle like 3->10->3 – SaiBot Dec 13 '17 at 14:53
  • 1
    Possible duplicate of [graph - How to find Minimum Directed Cycle (minimum total weight)?](https://stackoverflow.com/questions/10456935/graph-how-to-find-minimum-directed-cycle-minimum-total-weight) – Bonje Fir Dec 13 '17 at 15:04
  • The Floyd-Warshall algorithm finds shortest path between all pairs of vertices. I am looking for something that shows all the cycles of a specific node not something that shows the path from A to B. More like the path from node A to node A ( the differents cycles ) – Kamil Dec 15 '17 at 13:14

0 Answers0