Open In App

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

Last Updated : 04 Sep, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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:

Example1

Example 1

Output: No

Input:

Example2

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.

Bellman-Ford-To-Detect-A-Negative-Cycle-In-A-Graph

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.

file

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
file

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
file

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
file

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
file

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.
file

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.

file

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:





                                    


                                                                        

                                        

                                            

                                                

                                                    

        https://media.geeksforgeeks.org/auth/avatar.png
       
                                                

                                                

                                                    
    

        

            GeeksforGeeks
        

    
                                                

                                            

                                                                                    

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                                                            

                                    
                                        
                                        Previous Article
                                    
                                    
                                    

                                        Detect Cycle in a directed graph using colors
                                    

                                

                                                            

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Cycles of length n in an undirected and connected graph
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Minimum Cost Maximum Flow from a Graph using Bellman Ford Algorithm

                
Given a source node S, a sink node T, two matrices Cap[ ][ ] and Cost[ ][ ] representing a graph, where Cap[i][j] is the capacity of a directed edge from node i to node j and cost[i][j] is the cost of sending one unit of flow along a directed edge from node i to node j, the task is to find a flow with the minimum-cost maximum-flow possible from the

            

            
            

                
                15+ min read
            

        
    
        
            

                
Bellman Ford Algorithm (Simple Implementation)

                
We have introduced Bellman Ford and discussed on implementation here.Input: Graph and a source vertex src Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported.1) This step initializes distances from source to all vertices as infinite an

            

            
            

                
                13 min read
            

        
    
        
            

                
What are the differences between Bellman Ford's and Dijkstra's algorithms?

                
Bellman Ford's algorithm Like other Dynamic Programming Problems, the algorithm calculates shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with a

            

            
            

                
                3 min read
            

        
    
        
            

                
Edge Relaxation Property for Dijkstra’s Algorithm and Bellman Ford's Algorithm

                
In the field of graph theory, various shortest path algorithms especially Dijkstra’s algorithm and Bellmann-Ford’s algorithm repeatedly employ the use of the technique called Edge Relaxation. The idea of relaxation is the same in both algorithms and it is by understanding, the 'Relaxation property' we can fully grasp the working of the two algorith

            

            
            

                
                4 min read
            

        
    
        
            

                
Bellman-Ford vs Floyd-Warshall's algorithm: A Comparative Analysis

                
Bellman-Ford Algorithm:The Bellman-Ford algorithm is a single-source shortest-path algorithm that works by iteratively relaxing edges in the graph until the shortest path to all vertices is found. It is especially useful for graphs with negative edge weights, as it can detect negative cycles and return a suitable error message. Floyd-Warshall Algor

            

            
            

                
                15+ min read
            

        
    
        
            

                
Time and Space Complexity of Bellman–Ford Algorithm

                
The Bellman-Ford algorithm has a time complexity of O(V*E), where V is the number of vertices and E is the number of edges in the graph. In the worst-case scenario, the algorithm needs to iterate through all edges for each vertex, resulting in this time complexity. The space complexity of the Bellman-Ford algorithm is O(V), where V is the number of

            

            
            

                
                2 min read
            

        
    
        
            

                
Bellman–Ford Algorithm

                
Imagine you have a map with different cities connected by roads, each road having a certain distance. The Bellman–Ford algorithm is like a guide that helps you find the shortest path from one city to all other cities, even if some roads have negative lengths. It's like a GPS for computers, useful for figuring out the quickest way to get from one po

            

            
            

                
                15+ min read
            

        
    
        
            

                
Bellman-Ford algorithm in Python

                
Imagine you have a map with different cities connected by roads, each road having a certain distance. The Bellman–Ford algorithm is helps you find the shortest path from one city to all other cities, even if some roads have negative lengths. In this article, we’ll take a closer look at how this algorithm works and why it’s so handy in solving every

            

            
            

                
                2 min read
            

        
    
        
            

                
Detect a negative cycle in a Graph using Shortest Path Faster Algorithm

                
Given a graph G consisting of nodes valued [0, N - 1], a source S, and an array Edges[][3] of type {u, v, w} that denotes that there is a directed edge between node u and v with weight w, the task is to check if there exists a negative cycle from the given source. If found to be true, then print "Yes". Otherwise, print "No". A negative cycle is a c

            

            
            

                
                11 min read
            

        
    
        
            

                
Detect cycle in the graph using degrees of nodes of graph

                
Given a graph, the task is to detect a cycle in the graph using degrees of the nodes in the graph and print all the nodes that are involved in any of the cycles. If there is no cycle in the graph then print -1. Examples: Input: Output: 0 1 2 Approach: Recursively remove all vertices of degree 1. This can be done efficiently by storing a map of vert

            

            
            

                
                11 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
three90RightbarBannerImg

	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox