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:



Previous Article
Next Article

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