**Introduction**-

This blog will discuss how to detect a negative cycle using shortest path faster algorithm in a given __graph__. We will be given a weighted and directed graph, and we have to find if it contains a negative cycle or not using the shortest path faster algorithm. Before proceeding, let's recall what a negative cycle in a graph means.

"A cycle in a graph is known as a negative cycle if the sum of all the edge weights in that cycle is negative".

Now, let's understand the problem with an example:

In this problem, to detect a negative cycle using shortest path faster algorithm, we will be given a graph with 'N' nodes with values [0, N-1], a source vertex 'S', and a 2-D array denoting there is a directed edge from 'edge[i][0]' to 'edge[i][1]' with weight' edge[0][2]'. And, our task is to detect a negative cycle using shortest path faster algorithm in the given graph.

Example:

We have the graph given below and source vertex ‘s’ = 1

We can see here that in cycle 1->2->3->1, the sum of all the edge weights is equal to '-4' (-3-2+1). So, we have detected a negative cycle in the given graph starting from the given source.

So, now we have understood what a negative cycle is and what we have to detect in the given graph. In this blog, we will see an approach to detect the negative cycle using a particular algorithm, i.e., "shortest path faster algorithm".

**Solution Approach using shortest path faster algorithm**

This approach is a modification of the __Bellman-Ford Algorithm__. We will similarly relax the vertices, but there is a modification that in "Bellman-Ford algorithm", we tried relaxing the vertices "N-1" times where 'N' is the number of vertices in the graph. In contrast, in this approach, we will store the vertex that has been relaxed, and in the next step, we will relax only those vertices adjacent to the stored vertex.

In this approach to detect a negative cycle, we will be trying to relax each vertex, and if a vertex will be relaxed, we will insert that vertex into a queue so that now we can relax all the vertices which are adjacent to that vertex. In this way, we will keep relaxing the vertices until the queue becomes empty.

Here "relaxing a vertex" means to check for an edge 'u' to 'v', if the distance of v is greater than the sum of the weight of u-v edge and distance of 'u', then update the distance of 'v' as the sum of the distance of 'u' and weight of the edge 'u-v'.