Data Modelling & AI Data Structure & Algorithm

Detect a negative cycle in a Graph | (Bellman Ford)

21 June 2025

0

Given a directed weighted graph, the task is to find whether the given graph contains any negative-weight cycle or not.

Note: A negative-weight cycle is a cycle in a graph whose edges sum to a negative value.

Example:

Input:

Example 1

Output: No

Input:

Example 2

Output: Yes

Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford:

Initialize distance array dist[] for each vertex ‘v‘ as dist[v] = INFINITY.
Assume any vertex (let’s say ‘0’) as source and assign dist = 0.
Relax all the edges(u,v,weight) N-1 times as per the below condition:
- dist[v] = minimum(dist[v], distance[u] + weight)
Now, Relax all the edges one more time i.e. the Nth time and based on the below two cases we can detect the negative cycle:
- Case 1 (Negative cycle exists): For any edge(u, v, weight), if dist[u] + weight < dist[v]
- Case 2 (No Negative cycle) : case 1 fails for all the edges.

Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph:

Let’s suppose we have a graph which is given below and we want to find whether there exists a negative cycle or not using Bellman-Ford.

Initial Graph

Step-1: Initialize a distance array Dist[] to store the shortest distance for each vertex from the source vertex. Initially distance of source will be 0 and Distance of other vertices will be INFINITY.

Initialize a distance array

Step 2: Start relaxing the edges, during 1st Relaxation:

Current Distance of B > (Distance of A) + (Weight of A to B) i.e. Infinity > 0 + 5

Therefore, Dist[B] = 5

1st Relaxation

Step 3: During 2nd Relaxation:

Current Distance of D > (Distance of B) + (Weight of B to D) i.e. Infinity > 5 + 2

Dist[D] = 7

Current Distance of C > (Distance of B) + (Weight of B to C) i.e. Infinity > 5 + 1

Dist[C] = 6

2nd Relaxation

Step 4: During 3rd Relaxation:

Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. Infinity > 7 + 2

Dist[F] = 9

Current Distance of E > (Distance of C ) + (Weight of C to E) i.e. Infinity > 6 + 1

Dist[E] = 7

3rd Relaxation

Step 5: During 4th Relaxation:

Current Distance of D > (Distance of E) + (Weight of E to D) i.e. 7 > 7 + (-1)

Dist[D] = 6

Current Distance of E > (Distance of F ) + (Weight of F to E) i.e. 7 > 9 + (-3)

Dist[E] = 6

4th Relaxation

Step 6: During 5th Relaxation:

Current Distance of F > (Distance of D) + (Weight of D to F) i.e. 9 > 6 + 2

Dist[F] = 8

Current Distance of D > (Distance of E ) + (Weight of E to D) i.e. 6 > 6 + (-1)

Dist[E] = 5

Since the graph h 6 vertices, So during the 5th relaxation the shortest distance for all the vertices should have been calculated.

5th Relaxation

Step 7: Now the final relaxation i.e. the 6th relaxation should indicate the presence of negative cycle if there is any changes in the distance array of 5th relaxation.

During the 6th relaxation, following changes can be seen:

Current Distance of E > (Distance of F) + (Weight of F to E) i.e. 6 > 8 + (-3)

Dist[E]=5

Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. 8 > 5 + 2

Dist[F]=7

Since we observer changes in the Distance array Hence ,we can conclude the presence of a negative cycle in the graph.

6th Relaxation

Result: A negative cycle (D->F->E) exists in the graph.

Below is the implementation to detect Negative cycle in a graph:

C++

// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
using namespace std;
 
// A structure to represent a weighted edge in graph
struct Edge {
    int src, dest, weight;
};
 
// A structure to represent a connected, directed and
// weighted graph
struct Graph {
    // V-> Number of vertices, E-> Number of edges
    int V, E;
 
    // Graph is represented as an array of edges.
    struct Edge* edge;
};
 
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[graph->E];
    return graph;
}
 
// The main function that finds shortest distances
// from src to all other vertices using Bellman-
// Ford algorithm. The function also detects
// negative weight cycle
bool isNegCycleBellmanFord(struct Graph* graph, int src,
                           int dist[])
{
    int V = graph->V;
    int E = graph->E;
 
    // Step 1: Initialize distances from src
    // to all other vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;
 
    // Step 2: Relax all edges |V| - 1 times.
    // A simple shortest path from src to any
    // other vertex can have at-most |V| - 1
    // edges
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX
                && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
 
    // Step 3: check for negative-weight cycles.
    // The above step guarantees shortest distances
    // if graph doesn't contain negative weight cycle.
    // If we get a shorter path, then there
    // is a cycle.
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX
            && dist[u] + weight < dist[v])
            return true;
    }
 
    return false;
}
 
// Returns true if given graph has negative weight
// cycle.
bool isNegCycleDisconnected(struct Graph* graph)
{
 
    int V = graph->V;
 
    // To keep track of visited vertices to avoid
    // recomputations.
    bool visited[V];
    memset(visited, 0, sizeof(visited));
 
    // This array is filled by Bellman-Ford
    int dist[V];
 
    // Call Bellman-Ford for all those vertices
    // that are not visited
    for (int i = 0; i < V; i++) {
        if (visited[i] == false) {
            // If cycle found
            if (isNegCycleBellmanFord(graph, i, dist))
                return true;
 
            // Mark all vertices that are visited
            // in above call.
            for (int i = 0; i < V; i++)
                if (dist[i] != INT_MAX)
                    visited[i] = true;
        }
    }
 
    return false;
}
 
// Driver Code
int main()
{
 
    // Number of vertices in graph
    int V = 5;
 
    // Number of edges in graph
    int E = 8;
 
    // Let us create the graph given in above example
    struct Graph* graph = createGraph(V, E);
 
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;
 
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;
 
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;
 
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;
 
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;
 
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;
 
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;
 
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;
 
    if (isNegCycleDisconnected(graph))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// A Java program for Bellman-Ford's single source
// shortest path algorithm.
import java.util.*;
 
class GFG {
 
    // A structure to represent a weighted
    // edge in graph
    static class Edge {
        int src, dest, weight;
    }
 
    // A structure to represent a connected,
    // directed and weighted graph
    static class Graph {
 
        // V-> Number of vertices,
        // E-> Number of edges
        int V, E;
 
        // Graph is represented as
        // an array of edges.
        Edge edge[];
    }
 
    // Creates a graph with V vertices and E edges
    static Graph createGraph(int V, int E)
    {
        Graph graph = new Graph();
        graph.V = V;
        graph.E = E;
        graph.edge = new Edge[graph.E];
 
        for (int i = 0; i < graph.E; i++) {
            graph.edge[i] = new Edge();
        }
 
        return graph;
    }
 
    // The main function that finds shortest distances
    // from src to all other vertices using Bellman-
    // Ford algorithm. The function also detects
    // negative weight cycle
    static boolean
    isNegCycleBellmanFord(Graph graph, int src, int dist[])
    {
        int V = graph.V;
        int E = graph.E;
 
        // Step 1: Initialize distances from src
        // to all other vertices as INFINITE
        for (int i = 0; i < V; i++)
            dist[i] = Integer.MAX_VALUE;
 
        dist[src] = 0;
 
        // Step 2: Relax all edges |V| - 1 times.
        // A simple shortest path from src to any
        // other vertex can have at-most |V| - 1
        // edges
        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
 
                if (dist[u] != Integer.MAX_VALUE
                    && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }
 
        // Step 3: check for negative-weight cycles.
        // The above step guarantees shortest distances
        // if graph doesn't contain negative weight cycle.
        // If we get a shorter path, then there
        // is a cycle.
        for (int i = 0; i < E; i++) {
            int u = graph.edge[i].src;
            int v = graph.edge[i].dest;
            int weight = graph.edge[i].weight;
 
            if (dist[u] != Integer.MAX_VALUE
                && dist[u] + weight < dist[v])
                return true;
        }
 
        return false;
    }
 
    // Returns true if given graph has negative weight
    // cycle.
    static boolean isNegCycleDisconnected(Graph graph)
    {
        int V = graph.V;
 
        // To keep track of visited vertices
        // to avoid recomputations.
        boolean visited[] = new boolean[V];
        Arrays.fill(visited, false);
 
        // This array is filled by Bellman-Ford
        int dist[] = new int[V];
 
        // Call Bellman-Ford for all those vertices
        // that are not visited
        for (int i = 0; i < V; i++) {
            if (visited[i] == false) {
 
                // If cycle found
                if (isNegCycleBellmanFord(graph, i, dist))
                    return true;
 
                // Mark all vertices that are visited
                // in above call.
                for (int j = 0; j < V; j++)
                    if (dist[j] != Integer.MAX_VALUE)
                        visited[j] = true;
            }
        }
        return false;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int V = 5, E = 8;
        Graph graph = createGraph(V, E);
 
        // Add edge 0-1 (or A-B in above figure)
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = -1;
 
        // Add edge 0-2 (or A-C in above figure)
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;
 
        // Add edge 1-2 (or B-C in above figure)
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = 3;
 
        // Add edge 1-3 (or B-D in above figure)
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;
 
        // Add edge 1-4 (or A-E in above figure)
        graph.edge[4].src = 1;
        graph.edge[4].dest = 4;
        graph.edge[4].weight = 2;
 
        // Add edge 3-2 (or D-C in above figure)
        graph.edge[5].src = 3;
        graph.edge[5].dest = 2;
        graph.edge[5].weight = 5;
 
        // Add edge 3-1 (or D-B in above figure)
        graph.edge[6].src = 3;
        graph.edge[6].dest = 1;
        graph.edge[6].weight = 1;
 
        // Add edge 4-3 (or E-D in above figure)
        graph.edge[7].src = 4;
        graph.edge[7].dest = 3;
        graph.edge[7].weight = -3;
 
        if (isNegCycleDisconnected(graph))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by adityapande88

Python

# A Python3 program for Bellman-Ford's single source
# shortest path algorithm.
 
# The main function that finds shortest distances
# from src to all other vertices using Bellman-
# Ford algorithm. The function also detects
# negative weight cycle
 
 
def isNegCycleBellmanFord(src, dist):
    global graph, V, E
 
    # Step 1: Initialize distances from src
    # to all other vertices as INFINITE
    for i in range(V):
        dist[i] = 10**18
    dist[src] = 0
 
    # Step 2: Relax all edges |V| - 1 times.
    # A simple shortest path from src to any
    # other vertex can have at-most |V| - 1
    # edges
    for i in range(1, V):
        for j in range(E):
            u = graph[j][0]
            v = graph[j][1]
            weight = graph[j][2]
            if (dist[u] != 10**18 and dist[u] + weight < dist[v]):
                dist[v] = dist[u] + weight
 
    # Step 3: check for negative-weight cycles.
    # The above step guarantees shortest distances
    # if graph doesn't contain negative weight cycle.
    # If we get a shorter path, then there
    # is a cycle.
    for i in range(E):
        u = graph[i][0]
        v = graph[i][1]
        weight = graph[i][2]
        if (dist[u] != 10**18 and dist[u] + weight < dist[v]):
            return True
 
    return False
# Returns true if given graph has negative weight
# cycle.
 
 
def isNegCycleDisconnected():
    global V, E, graph
 
    # To keep track of visited vertices to avoid
    # recomputations.
    visited = [0]*V
    # memset(visited, 0, sizeof(visited))
 
    # This array is filled by Bellman-Ford
    dist = [0]*V
 
    # Call Bellman-Ford for all those vertices
    # that are not visited
    for i in range(V):
        if (visited[i] == 0):
 
            # If cycle found
            if (isNegCycleBellmanFord(i, dist)):
                return True
 
            # Mark all vertices that are visited
            # in above call.
            for i in range(V):
                if (dist[i] != 10**18):
                    visited[i] = True
    return False
 
 
# Driver code
if __name__ == '__main__':
 
    # /* Let us create the graph given in above example */
    V = 5  # Number of vertices in graph
    E = 8  # Number of edges in graph
    graph = [[0, 0, 0] for i in range(8)]
 
    # add edge 0-1 (or A-B in above figure)
    graph[0][0] = 0
    graph[0][1] = 1
    graph[0][2] = -1
 
    # add edge 0-2 (or A-C in above figure)
    graph[1][0] = 0
    graph[1][1] = 2
    graph[1][2] = 4
 
    # add edge 1-2 (or B-C in above figure)
    graph[2][0] = 1
    graph[2][1] = 2
    graph[2][2] = 3
 
    # add edge 1-3 (or B-D in above figure)
    graph[3][0] = 1
    graph[3][1] = 3
    graph[3][2] = 2
 
    # add edge 1-4 (or A-E in above figure)
    graph[4][0] = 1
    graph[4][1] = 4
    graph[4][2] = 2
 
    # add edge 3-2 (or D-C in above figure)
    graph[5][0] = 3
    graph[5][1] = 2
    graph[5][2] = 5
 
    # add edge 3-1 (or D-B in above figure)
    graph[6][0] = 3
    graph[6][1] = 1
    graph[6][2] = 1
 
    # add edge 4-3 (or E-D in above figure)
    graph[7][0] = 4
    graph[7][1] = 3
    graph[7][2] = -3
 
    if (isNegCycleDisconnected()):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

C#

// A C# program for Bellman-Ford's single source
// shortest path algorithm.
using System;
using System.Collections.Generic;
public class GFG {
 
    // A structure to represent a weighted
    // edge in graph
    public class Edge {
        public int src, dest, weight;
    }
 
    // A structure to represent a connected,
    // directed and weighted graph
    public class Graph {
 
        // V-> Number of vertices,
        // E-> Number of edges
        public int V, E;
 
        // Graph is represented as
        // an array of edges.
        public Edge[] edge;
    }
 
    // Creates a graph with V vertices and E edges
    static Graph createGraph(int V, int E)
    {
        Graph graph = new Graph();
        graph.V = V;
        graph.E = E;
        graph.edge = new Edge[graph.E];
        for (int i = 0; i < graph.E; i++) {
            graph.edge[i] = new Edge();
        }
 
        return graph;
    }
 
    // The main function that finds shortest distances
    // from src to all other vertices using Bellman-
    // Ford algorithm. The function also detects
    // negative weight cycle
    static bool isNegCycleBellmanFord(Graph graph, int src,
                                      int[] dist)
    {
        int V = graph.V;
        int E = graph.E;
 
        // Step 1: Initialize distances from src
        // to all other vertices as INFINITE
        for (int i = 0; i < V; i++)
            dist[i] = int.MaxValue;
 
        dist[src] = 0;
 
        // Step 2: Relax all edges |V| - 1 times.
        // A simple shortest path from src to any
        // other vertex can have at-most |V| - 1
        // edges
        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
 
                if (dist[u] != int.MaxValue
                    && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }
 
        // Step 3: check for negative-weight cycles.
        // The above step guarantees shortest distances
        // if graph doesn't contain negative weight cycle.
        // If we get a shorter path, then there
        // is a cycle.
        for (int i = 0; i < E; i++) {
            int u = graph.edge[i].src;
            int v = graph.edge[i].dest;
            int weight = graph.edge[i].weight;
 
            if (dist[u] != int.MaxValue
                && dist[u] + weight < dist[v])
                return true;
        }
 
        return false;
    }
 
    // Returns true if given graph has negative weight
    // cycle.
    static bool isNegCycleDisconnected(Graph graph)
    {
        int V = graph.V;
 
        // To keep track of visited vertices
        // to avoid recomputations.
        bool[] visited = new bool[V];
 
        // This array is filled by Bellman-Ford
        int[] dist = new int[V];
 
        // Call Bellman-Ford for all those vertices
        // that are not visited
        for (int i = 0; i < V; i++) {
            if (visited[i] == false) {
 
                // If cycle found
                if (isNegCycleBellmanFord(graph, i, dist))
                    return true;
 
                // Mark all vertices that are visited
                // in above call.
                for (int j = 0; j < V; j++)
                    if (dist[j] != int.MaxValue)
                        visited[j] = true;
            }
        }
        return false;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int V = 5, E = 8;
        Graph graph = createGraph(V, E);
 
        // Add edge 0-1 (or A-B in above figure)
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = -1;
 
        // Add edge 0-2 (or A-C in above figure)
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;
 
        // Add edge 1-2 (or B-C in above figure)
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = 3;
 
        // Add edge 1-3 (or B-D in above figure)
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;
 
        // Add edge 1-4 (or A-E in above figure)
        graph.edge[4].src = 1;
        graph.edge[4].dest = 4;
        graph.edge[4].weight = 2;
 
        // Add edge 3-2 (or D-C in above figure)
        graph.edge[5].src = 3;
        graph.edge[5].dest = 2;
        graph.edge[5].weight = 5;
 
        // Add edge 3-1 (or D-B in above figure)
        graph.edge[6].src = 3;
        graph.edge[6].dest = 1;
        graph.edge[6].weight = 1;
 
        // Add edge 4-3 (or E-D in above figure)
        graph.edge[7].src = 4;
        graph.edge[7].dest = 3;
        graph.edge[7].weight = -3;
 
        if (isNegCycleDisconnected(graph))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by aashish1995

Javascript

<script>
// A Javascript program for Bellman-Ford's single source
// shortest path algorithm.
     
    // A structure to represent a weighted
    // edge in graph
    class Edge
    {
        constructor()
        {
            let src, dest, weight;
        }
    }
     
    // A structure to represent a connected,
    // directed and weighted graph
    class Graph
    {
        constructor()
        {
            // V-> Number of vertices,
            // E-> Number of edges
            let V, E;
             
            // Graph is represented as
            // an array of edges.
            let edge=[];
        }
    }
     
    // Creates a graph with V vertices and E edges
    function createGraph(V,E)
    {
        let graph = new Graph();
        graph.V = V;
           graph.E = E;
        graph.edge = new Array(graph.E);
  
    for(let i = 0; i < graph.E; i++)
    {
        graph.edge[i] = new Edge();
    }
  
    return graph;
    }
 
// The main function that finds shortest distances
// from src to all other vertices using Bellman-
// Ford algorithm. The function also detects
// negative weight cycle
function isNegCycleBellmanFord(graph,src,dist)
{
    let V = graph.V;
    let E = graph.E;
    
    // Step 1: Initialize distances from src
    // to all other vertices as INFINITE
    for(let i = 0; i < V; i++)
        dist[i] = Number.MAX_VALUE;
          
    dist[src] = 0;
    
    // Step 2: Relax all edges |V| - 1 times.
    // A simple shortest path from src to any
    // other vertex can have at-most |V| - 1
    // edges
    for(let i = 1; i <= V - 1; i++)
    {
        for(let j = 0; j < E; j++)
        {
            let u = graph.edge[j].src;
            let v = graph.edge[j].dest;
            let weight = graph.edge[j].weight;
            
            if (dist[u] != Number.MAX_VALUE &&
                dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
    
    // Step 3: check for negative-weight cycles.
    // The above step guarantees shortest distances
    // if graph doesn't contain negative weight cycle.
    // If we get a shorter path, then there
    // is a cycle.
    for(let i = 0; i < E; i++)
    {
        let u = graph.edge[i].src;
        let v = graph.edge[i].dest;
        let weight = graph.edge[i].weight;
        
        if (dist[u] != Number.MAX_VALUE &&
            dist[u] + weight < dist[v])
            return true;
    }
    
    return false;
}
 
// Returns true if given graph has negative weight
// cycle.
function isNegCycleDisconnected(graph)
{
    let V = graph.V;
      
    // To keep track of visited vertices
    // to avoid recomputations.
    let visited = new Array(V);
    for(let i=0;i<V;i++)
    {
        visited[i]=false;
    }
    
    // This array is filled by Bellman-Ford
    let dist = new Array(V);
  
    // Call Bellman-Ford for all those vertices
    // that are not visited
    for(let i = 0; i < V; i++)
    {
        if (visited[i] == false)
        {
              
            // If cycle found
            if (isNegCycleBellmanFord(graph, i, dist))
                return true;
    
            // Mark all vertices that are visited
            // in above call.
            for(let j = 0; j < V; j++)
                if (dist[j] != Number.MAX_VALUE)
                    visited[j] = true;
        }
    }
    return false;
}
 
// Driver Code
 
let V = 5, E = 8;
let graph = createGraph(V, E);
 
// Add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
 
// Add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
 
// Add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
 
// Add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
 
// Add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
 
// Add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
 
// Add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
 
// Add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
 
if (isNegCycleDisconnected(graph))
    document.write("Yes");
else
    document.write("No");
     
 
// This code is contributed by patel2127
</script>

Output

No

Time Complexity: O(V*E), , where V and E are the number of vertices in the graph and edges respectively.
Auxiliary Space: O(V), where V is the number of vertices in the graph.

Related articles:

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Detect a negative cycle in a Graph | (Bellman Ford)

Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford:

Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph:

C++

Java

Python

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US