Finding a Negative Cycle in the Graph

Find any cycle of negative weight in the given, if such a cycle exists.

Example:

Input:  edges={{1,2,3},{2,3,-5},{3,1,-2},{3,4,5}}
Output: Negative cycle: 3 1 2 3 

Approach

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FindNegCycleInGraph {
    static int n, m;

    // vector array to hold all
    // the edges
    static List<Edge> edges;

    static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        n = 4;
        m = 4;
        edges = new ArrayList<Edge>();
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(2, 3, -5));
        edges.add(new Edge(3, 1, -2));
        edges.add(new Edge(3, 4, 5));

        negativeCycle();
    }

    static void negativeCycle() {
        // array to hold the distance of
        // all nodes
        int[] dist = new int[n + 1];

        // array to hold the parent of
        // all nodes
        int[] parent = new int[n + 1];
        int x = 0;

        // iterate for all nodes
        for (int i = 0; i < n; ++i) {
            x = -1;

            // iterate for all the edges
            for (Edge e : edges) {

                // update the distance and
                // parent
                if (dist[e.a] + e.cost < dist[e.b]) {
                    dist[e.b] = dist[e.a] + e.cost;
                    parent[e.b] = e.a;
                    x = e.b;
                }
            }
        }
        // if no cycle
        if (x == -1) {
            System.out.print("No negative cycle found. ");
        }

        // else cycle is present
        else {
            for (int i = 0; i < n; ++i)
                x = parent[x];

            List<Integer> cycle = new ArrayList<Integer>();
            for (int v = x;; v = parent[v]) {
                cycle.add(v);
                if (v == x && cycle.size() > 1)
                    break;
            }
            Collections.reverse(cycle);

            System.out.print("Negative cycle: ");
            for (int v : cycle)
                System.out.print(v + " ");
            System.out.println();
        }
    }

    // static class of the edges
    static class Edge {
        int a, b, cost;

        public Edge(int a, int b, int cost) {
            super();
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        public int getA() {
            return a;
        }

        public void setA(int a) {
            this.a = a;
        }

        public int getB() {
            return b;
        }

        public void setB(int b) {
            this.b = b;
        }

        public int getCost() {
            return cost;
        }

        public void setCost(int cost) {
            this.cost = cost;
        }

    }

}

C++

#include <bits/stdc++.h>
using namespace std;

//structute of the edges
struct Edge
{
    int a, b, cost;
};

int n, m;

//vector array to hold all
//the edges
vector<Edge> edges;
const int INF = INT_MAX;

void negativeCycle()
{
    //array to hold the distance of
    //all nodes
    vector<int> dist(n + 1);

    //array to hold the parent of
    //all nodes
    vector<int> parent(n + 1, -1);
    int x;

    //iterate for all nodes
    for (int i = 0; i < n; ++i)
    {
        x = -1;

        //iterate for all the edges
        for (Edge e : edges)
        {

            //update the distance and
            //parent
            if (dist[e.a] + e.cost < dist[e.b])
            {
                dist[e.b] = dist[e.a] + e.cost;
                parent[e.b] = e.a;
                x = e.b;
            }
        }
    }
    //if no cycle
    if (x == -1)
    {
        cout << "No negative cycle found.";
    }

    //else cycle is present
    else
    {
        for (int i = 0; i < n; ++i)
            x = parent[x];

        vector<int> cycle;
        for (int v = x;; v = parent[v])
        {
            cycle.push_back(v);
            if (v == x && cycle.size() > 1)
                break;
        }
        reverse(cycle.begin(), cycle.end());

        cout << "Negative cycle: ";
        for (int v : cycle)
            cout << v << ' ';
        cout << endl;
    }
}

int main()
{
    n = 4, m = 4;
    edges.push_back({1, 2, 3});
    edges.push_back({2, 3, -5});
    edges.push_back({3, 1, -2});
    edges.push_back({3, 4, 5});
    negativeCycle();
    return 0;
}