# find shortest cycle in directed graph

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 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: https://www.quora.com/Can-Floyd-Warshall-algorithm-be-used-to-find-shortest-cycle-in-an-undirected-graph)

*Sample implementation*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<cstring> using namespace std; #define V 8 #define inf 999999 // adjacency matrix as distance matrix for the graph int dist[V][V] ={{inf, inf, 1, inf, inf, inf, inf, inf}, {inf, inf, inf, inf, inf, inf, inf, inf}, {inf, 1, inf, 1, inf, inf, 1, inf}, {1, inf, inf, inf, inf, inf, inf, inf}, {inf, inf, 1, inf, inf, inf, inf, inf}, {inf, inf, 1, inf, inf, inf, inf, 1}, {inf, 1, inf, inf, inf, inf, inf, 1}, {inf, inf, inf, inf, 1, inf, inf, inf} }; int main () { // run Floyd-Warshal algo on graph for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } // print minimum dist[v][v] int min = 999999; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (i == j) { if (min > dist[i][j]) min = dist[i][j]; } } } cout << min << endl; return 0; } |

## Leave a Reply