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)