Imprimir ciclo de peso negativo en un gráfico dirigido

Dado un gráfico dirigido ponderado que consta de V vértices y E aristas. La tarea es imprimir el camino cíclico cuya suma de peso es negativa. Si no existe tal ruta presente, imprima «-1»

Entrada: V = 5, E = 5, A continuación se muestra el gráfico: 
 

Aquí, para el ciclo negativo dado o/p (1->2->3->4->1); En la figura tiene que haber Edge de 4–>1 no de 4–>0 

Salida: 1 2 3 4 1 
Explicación: 
El gráfico dado contiene un ciclo negativo, (1->2->3->4->1)

Entrada: V = 5, E = 5, A continuación se muestra el gráfico: 
 

Salida: 0 1 2 3 4 0 
Explicación: 
El gráfico dado contiene un ciclo negativo, (0->1->2->3->4->0) 
 

Enfoque: La idea es utilizar el Algoritmo de Bellman-Ford que se utiliza para detectar un ciclo negativo o no. Para imprimir los ciclos negativos, realice la enésima iteración de Bellman-Ford y elija un vértice de cualquier borde que esté relajado en esta iteración. Usando este vértice y sus ancestros, se puede imprimir el ciclo negativo. A continuación se muestran los pasos: 

  • Realice N-1 iteraciones del algoritmo Bellman-Ford y relaje cada borde (u, v) . Realice un seguimiento del padre de cada vértice y almacénelo en una array parent[] .
  • Ahora, haga una iteración más y si no se produce relajación de borde en esta enésima iteración , entonces no existe un ciclo de peso negativo en el gráfico.
  • De lo contrario, tome una variable C y almacene el vértice v desde cualquier borde (u, v) , que se relaja en la iteración N- ésima .
  • Ahora, partiendo del vértice C ir hacia sus ancestros hasta encontrar un ciclo y finalmente imprimirlo.
  • Este ciclo será el ciclo deseado de peso negativo.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Structure to represent a weighted
// edge in graph
struct Edge {
    int src, dest, weight;
};
  
// Structure to represent a 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 new 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;
}
  
vector<int> vis;
// Function runs Bellman-Ford algorithm
// and prints negative cycle(if present)
void NegCycleBellmanFord(struct Graph* graph,
                        int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[V];
    int parent[V];
  
    // Initialize distances from src
    // to all other vertices as INFINITE
    // and all parent as -1
    for (int i = 0; i < V; i++) {
  
        dist[i] = INT_MAX;
        parent[i] = -1;
    }
    dist[src] = 0;
    vis[src] = 0;
    // Relax all edges |V| - 1 times.
    bool flg = true;
    for (int i = 1; i <= V - 1; i++) {
      if(flg==false)
            break;
      flg=false;
        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]) {
                flg = true;
                vis[v] = 1;
                dist[v] = dist[u] + weight;
                parent[v] = u;
            }
        }
    }
  
    // Check for negative-weight cycles
    int C = -1;
    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]) {
  
            // Store one of the vertex of
            // the negative weight cycle
            C = v;
            break;
        }
    }
  
    if (C != -1) {
  
        for (int i = 0; i < V; i++)
            C = parent[C];
  
        // To store the cycle vertex
        vector<int> cycle;
        for (int v = C;; v = parent[v]) {
  
            cycle.push_back(v);
            if (v == C
                && cycle.size() > 1)
                break;
        }
  
        // Reverse cycle[]
        reverse(cycle.begin(), cycle.end());
  
        // Printing the negative cycle
        for (int v : cycle)
            cout << v << ' ';
        cout << endl;
       exit(0);
    }
}
  
// Driver Code
int main()
{
    // Number of vertices in graph
    int V = 5;
  
    // Number of edges in graph
    int E = 5;
  
    struct Graph* graph = createGraph(V, E);
    vis.resize(V,0);
    // Given Graph
    graph->edge[0].src = 1;
    graph->edge[0].dest = 0;
    graph->edge[0].weight = 1;
  
    graph->edge[1].src = 1;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 2;
  
    graph->edge[2].src = 2;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 3;
  
    graph->edge[3].src = 3;
    graph->edge[3].dest = 4;
    graph->edge[3].weight = -3;
  
    graph->edge[4].src = 4;
    graph->edge[4].dest = 1;
    graph->edge[4].weight = -3;
  
    // Function Call
    for(int src = 0;src<V;src++)
    {
      if(vis[src]==0)
         NegCycleBellmanFord(graph, src);
    } 
        cout << "-1\n";
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
  
class GFG{
  
// Structure to represent a weighted
// edge in graph
static class Edge 
{
    int src, dest, weight;
}
  
// Structure to represent a 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 new 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;
}
  
// Function runs Bellman-Ford algorithm
// and prints negative cycle(if present)
static void NegCycleBellmanFord(Graph graph, int src)
{
    int V = graph.V;
    int E = graph.E;
    int[] dist = new int[V];
    int[] parent = new int[V];
  
    // Initialize distances from src
    // to all other vertices as INFINITE
    // and all parent as -1
    for(int i = 0; i < V; i++) 
    {
        dist[i] = 1000000;
        parent[i] = -1;
    }
    dist[src] = 0;
  
    // Relax all edges |V| - 1 times.
    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] != 1000000 && 
                dist[u] + weight < dist[v])
            {
                dist[v] = dist[u] + weight;
                parent[v] = u;
            }
        }
    }
  
    // Check for negative-weight cycles
    int C = -1;
    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] != 1000000 && 
            dist[u] + weight < dist[v])
        {
              
            // Store one of the vertex of
            // the negative weight cycle
            C = v;
            break;
        }
    }
  
    if (C != -1)
    {
        for(int i = 0; i < V; i++)
            C = parent[C];
  
        // To store the cycle vertex
        ArrayList<Integer> cycle = new ArrayList<>();
        for(int v = C;; v = parent[v])
        {
            cycle.add(v);
              
            if (v == C && cycle.size() > 1)
                break;
        }
  
        // Reverse cycle[]
        Collections.reverse(cycle);
  
        // Printing the negative cycle
        for(int v : cycle)
            System.out.print(v + " ");
              
        System.out.println();
    } 
    else
        System.out.println(-1);
}
  
// Driver Code
public static void main(String[] args)
{
      
    // Number of vertices in graph
    int V = 5;
  
    // Number of edges in graph
    int E = 5;
  
    Graph graph = createGraph(V, E);
  
    // Given Graph
    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;
  
    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 2;
  
    graph.edge[2].src = 2;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 3;
  
    graph.edge[3].src = 3;
    graph.edge[3].dest = 4;
    graph.edge[3].weight = -3;
  
    graph.edge[4].src = 4;
    graph.edge[4].dest = 1;
    graph.edge[4].weight = -3;
  
    // Function Call
    NegCycleBellmanFord(graph, 0);
}
}
  
// This code is contributed by sanjeev2552

Python3

# Python3 program for the above approach
   
# Structure to represent a weighted
# edge in graph
class Edge:   
    def __init__(self):
        self.src = 0
        self.dest = 0
        self.weight = 0
  
# Structure to represent a directed
# and weighted graph
class Graph:
  
    def __init__(self):
          
        # V. Number of vertices, E.
        # Number of edges
        self.V = 0
        self.E = 0
          
        # Graph is represented as
        # an array of edges.
        self.edge = []
       
# Creates a new graph with V vertices
# and E edges
def createGraph(V, E):
    graph = Graph();
    graph.V = V;
    graph.E = E;
    graph.edge = [Edge() for i in range(graph.E)]
    return graph;
    
# Function runs Bellman-Ford algorithm
# and prints negative cycle(if present)
def NegCycleBellmanFord(graph, src):
    V = graph.V;
    E = graph.E;
    dist =[1000000 for i in range(V)]
    parent =[-1 for i in range(V)]
    dist[src] = 0;
   
    # Relax all edges |V| - 1 times.
    for i in range(1, V):
        for j in range(E):
      
            u = graph.edge[j].src;
            v = graph.edge[j].dest;
            weight = graph.edge[j].weight;
   
            if (dist[u] != 1000000 and
                dist[u] + weight < dist[v]):
              
                dist[v] = dist[u] + weight;
                parent[v] = u;
   
    # Check for negative-weight cycles
    C = -1;    
    for i in range(E):   
        u = graph.edge[i].src;
        v = graph.edge[i].dest;
        weight = graph.edge[i].weight;
   
        if (dist[u] != 1000000 and 
            dist[u] + weight < dist[v]):
               
            # Store one of the vertex of
            # the negative weight cycle
            C = v;
            break;
           
    if (C != -1):       
        for i in range(V):       
            C = parent[C];
   
        # To store the cycle vertex
        cycle = []       
        v = C
          
        while (True):
            cycle.append(v)
            if (v == C and len(cycle) > 1):
                break;
            v = parent[v]
   
        # Reverse cycle[]
        cycle.reverse()
   
        # Printing the negative cycle
        for v in cycle:       
            print(v, end = " ");             
        print()   
    else:
        print(-1);
   
# Driver Code
if __name__=='__main__':
       
    # Number of vertices in graph
    V = 5;
   
    # Number of edges in graph
    E = 5; 
    graph = createGraph(V, E);
   
    # Given Graph
    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;
   
    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 2;
   
    graph.edge[2].src = 2;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 3;
   
    graph.edge[3].src = 3;
    graph.edge[3].dest = 4;
    graph.edge[3].weight = -3;
   
    graph.edge[4].src = 4;
    graph.edge[4].dest = 1;
    graph.edge[4].weight = -3;
   
    # Function Call
    NegCycleBellmanFord(graph, 0);
  
# This code is contributed by Pratham76

C#

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
  
class GFG {
  
    // Structure to represent a weighted
    // edge in graph
    class Edge {
        public int src, dest, weight;
    }
    // Structure to represent a directed
    // and weighted graph
    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 new 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;
    }
  
    // Function runs Bellman-Ford algorithm
    // and prints negative cycle(if present)
    static void NegCycleBellmanFord(Graph graph, int src)
    {
        int V = graph.V;
        int E = graph.E;
        int[] dist = new int[V];
        int[] parent = new int[V];
  
        // Initialize distances from src
        // to all other vertices as INFINITE
        // and all parent as -1
        for (int i = 0; i < V; i++) {
  
            dist[i] = 1000000;
            parent[i] = -1;
        }
        dist[src] = 0;
  
        // Relax all edges |V| - 1 times.
        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] != 1000000
                    && dist[u] + weight < dist[v]) {
  
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                }
            }
        }
  
        // Check for negative-weight cycles
        int C = -1;
        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] != 1000000
                && dist[u] + weight < dist[v]) {
  
                // Store one of the vertex of
                // the negative weight cycle
                C = v;
                break;
            }
        }
  
        if (C != -1) {
  
            for (int i = 0; i < V; i++)
                C = parent[C];
  
            // To store the cycle vertex
            ArrayList cycle = new ArrayList();
            for (int v = C;; v = parent[v]) {
  
                cycle.Add(v);
                if (v == C && cycle.Count > 1)
                    break;
            }
  
            // Reverse cycle[]
            cycle.Reverse();
  
            // Printing the negative cycle
            foreach(int v in cycle) Console.Write(v + " ");
            Console.WriteLine();
        }
        else
            Console.WriteLine(-1);
    }
  
    // Driver Code
    public static void Main(string[] args)
    {
  
        // Number of vertices in graph
        int V = 5;
  
        // Number of edges in graph
        int E = 5;
  
        Graph graph = createGraph(V, E);
  
        // Given Graph
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 1;
  
        graph.edge[1].src = 1;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 2;
  
        graph.edge[2].src = 2;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 3;
  
        graph.edge[3].src = 3;
        graph.edge[3].dest = 4;
        graph.edge[3].weight = -3;
  
        graph.edge[4].src = 4;
        graph.edge[4].dest = 1;
        graph.edge[4].weight = -3;
  
        // Function Call
        NegCycleBellmanFord(graph, 0);
    }
}
  
// This code is contributed by rutvik_56

Javascript

<script>
  
// JavaScript program for the above approach
// Structure to represent a weighted
// edge in graph
class Edge {
    constructor()
    {
        this.src = 0;
        this.dest = 0;
        this.weight = 0;
    }
}
// Structure to represent a directed
// and weighted graph
class Graph {
      
    constructor()
    {
        // V. Number of vertices, E. Number of edges
        this.V = 0;
        this.E = 0;
        // graph is represented as an array of edges.
        this.edge = [];
    }
}
// Creates a new graph with V vertices
// and E edges
function createGraph(V, E)
{
    var graph = new Graph();
    graph.V = V;
    graph.E = E;
    graph.edge = Array(graph.E);
  
    for(var i = 0; i < graph.E; i++) {
        graph.edge[i] = new Edge();
    }
    return graph;
}
// Function runs Bellman-Ford algorithm
// and prints negative cycle(if present)
function NegCycleBellmanFord(graph, src)
{
    var V = graph.V;
    var E = graph.E;
    var dist = Array(V).fill(0);;
    var parent = Array(V).fill(0);;
    // Initialize distances from src
    // to all other vertices as INFINITE
    // and all parent as -1
    for (var i = 0; i < V; i++) {
        dist[i] = 1000000;
        parent[i] = -1;
    }
    dist[src] = 0;
    // Relax all edges |V| - 1 times.
    for (var i = 1; i <= V - 1; i++) {
        for (var j = 0; j < E; j++) {
            var u = graph.edge[j].src;
            var v = graph.edge[j].dest;
            var weight = graph.edge[j].weight;
            if (dist[u] != 1000000
                && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                parent[v] = u;
            }
        }
    }
    // Check for negative-weight cycles
    var C = -1;
    for (var i = 0; i < E; i++) {
        var u = graph.edge[i].src;
        var v = graph.edge[i].dest;
        var weight = graph.edge[i].weight;
        if (dist[u] != 1000000
            && dist[u] + weight < dist[v]) {
            // Store one of the vertex of
            // the negative weight cycle
            C = v;
            break;
        }
    }
    if (C != -1) {
        for (var i = 0; i < V; i++)
            C = parent[C];
        // To store the cycle vertex
        var cycle = [];
        for (var v = C;; v = parent[v]) {
            cycle.push(v);
            if (v == C && cycle.length > 1)
                break;
        }
        // Reverse cycle[]
        cycle.reverse();
        // Printing the negative cycle
        for(var v of cycle) document.write(v + " ");
        document.write("<br>");
    }
    else
        document.write(-1 + "<br>");
}
  
// Driver Code
// Number of vertices in graph
var V = 5;
// Number of edges in graph
var E = 5;
var graph = createGraph(V, E);
// Given Graph
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 1;
graph.edge[1].src = 1;
graph.edge[1].dest = 2;
graph.edge[1].weight = 2;
graph.edge[2].src = 2;
graph.edge[2].dest = 3;
graph.edge[2].weight = 3;
graph.edge[3].src = 3;
graph.edge[3].dest = 4;
graph.edge[3].weight = -3;
graph.edge[4].src = 4;
graph.edge[4].dest = 1;
graph.edge[4].weight = -3;
// Function Call
NegCycleBellmanFord(graph, 0);
  
</script>
Producción: 

1 2 3 4 1

 

Complejidad temporal: O(V*E)  
Espacio auxiliar: O(V)
 

Publicación traducida automáticamente

Artículo escrito por yash2040 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *