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

Sample implementation

#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;
}

 



Related Contents to follow