Find shortest cycle in directed graph. A cycle is a close path in graph. For example below given directed graph contains a cycle of length 3 starting from vertex 0, 2, 3 0 . Another cycle of length 4 in the graph is 2,6,7,4,2 . The program should return shortest cycle’s length.

find shortest cycle in directed graph

Find shortest cycle in directed graph using modified Floyd-Warshall algorithm

We know that Floyd-Warshall algorithm finds all pair shortest path in directed graph. In Floyd-Warshall we initially set dist[u][v] = ∞ and dist[v][v] = 0. It means that distance between u and v is infinity and distance to a vertex v to itself is 0. To find a cycle we need to modify dist[v][v] to infinity. This means that from v, we want the shortest path to v, which is the same as finding the shortest cycle which includes vertex v.  ( Ref:

Sample implementation


Related Contents to follow