Dado un gráfico G que consta de Nodes valorados [0, N – 1] , una fuente S y una array Edges[][3] de tipo { u, v, w } que denota que hay un borde dirigido entre el Node u y v con peso w , la tarea es verificar si existe un ciclo negativo de la fuente dada. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Un ciclo negativo es un ciclo en el que la suma de todo su peso en ese ciclo es negativa .
Ejemplos:
Entrada: N = 4, M = 4, Bordes[][] = {{0, 1, 1}, {1, 2, -1}, {2, 3, -1}, {3, 0, -1 }}, S = 0
Salida: Sí
Explicación:
Comenzando desde el Node fuente 0, el gráfico contiene el ciclo como 0 -> 1 -> 2 -> 3 -> 0.
La suma del peso en la ruta anterior es 1 – 1 – 1 – 1 = -2.
Por lo tanto, el gráfico contiene un ciclo negativo.Entrada: N = 4, M = 5, Bordes[][] = {{0, 2, -2}, {1, 0, 4}, {1, 2, -3}, {2, 3}, { 3, 1}}, W[] = {-2, 4, -3, 2, -1}, S = 1
Salida: Sí
Explicación:
Comenzando desde el Node fuente 1, el gráfico contiene el ciclo como 1 -> 2 -> 3 -> 1.
La suma del peso en la ruta anterior es -3 + 2 – 1 = -2.
Por lo tanto, el gráfico contiene un ciclo negativo.
Enfoque: la idea es utilizar el algoritmo más rápido de la ruta más corta (SPFA) para encontrar si un ciclo negativo está presente y es accesible desde el vértice de origen en un gráfico. Siga los pasos a continuación para resolver el problema:
- Inicialice las arrays dis[] con un valor grande, vis[] con false y cnt[] para almacenar el recuento de cuántas veces se ha relajado un vértice.
- Recorra el gráfico utilizando el algoritmo SPFA .
- Incremente el conteo para cada vértice siempre que el vértice esté relajado.
El término relajación significa actualizar el costo de todos los vértices conectados a un vértice v si esos costos mejorarían al incluir el camino a través del vértice v .
- Detenga el algoritmo e imprima «Sí» tan pronto como algún vértice se relaje por enésima vez, ya que solo hay N vértices, es decir, de 0 a N – 1 .
- De lo contrario, escriba “No” .
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; bool sfpa(int V, int src, int Edges[][3], int M) { // Stores the adjacency list of // the given graph vector<pair<int, int> > g[V]; // Create Adjacency List for (int i = 0; i < M; i++) { int u = Edges[i][0]; int v = Edges[i][1]; int w = Edges[i][2]; g[u].push_back({ v, w }); } // Stores the distance of all // reachable vertex from source vector<int> dist(V, INT_MAX); // Check if vertex is present // in queue or not vector<bool> inQueue(V, false); // Counts the relaxation for // each vertex vector<int> cnt(V, 0); // Distance from src to src is 0 dist[src] = 0; // Create a queue queue<int> q; // Push source in the queue q.push(src); // Mark source as visited inQueue[src] = true; while (!q.empty()) { // Front vertex of Queue int u = q.front(); q.pop(); inQueue[u] = false; // Relaxing all edges of // vertex from the Queue for (pair<int, int> x : g[u]) { int v = x.first; int cost = x.second; // Update the dist[v] to // minimum distance if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; // If vertex v is in Queue if (!inQueue[v]) { q.push(v); inQueue[v] = true; cnt[v]++; // Negative cycle if (cnt[v] >= V) return true; } } } } // No cycle found return false; } // Driver Code int main() { // Number of vertices int N = 4; // Given source node src int src = 0; // Number of Edges int M = 4; // Given Edges with weight int Edges[][3] = { { 0, 1, 1 }, { 1, 2, -1 }, { 2, 3, -1 }, { 3, 0, -1 } }; // If cycle is present if (sfpa(N, src, Edges, M) == true) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
// Java program for // the above approach import java.util.*; class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } static boolean sfpa(int V, int src, int Edges[][], int M) { // Stores the adjacency list of // the given graph Vector<pair> []g = new Vector[V]; for (int i = 0; i < V; i++) { g[i] = new Vector<pair>(); } // Create Adjacency List for (int i = 0; i < M; i++) { int u = Edges[i][0]; int v = Edges[i][1]; int w = Edges[i][2]; g[u].add(new pair(v, w)); } // Stores the distance of all // reachable vertex from source int []dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); // Check if vertex is present // in queue or not boolean []inQueue = new boolean[V]; // Counts the relaxation for // each vertex int []cnt = new int[V]; // Distance from src // to src is 0 dist[src] = 0; // Create a queue Queue<Integer> q = new LinkedList<>(); // Push source in the queue q.add(src); // Mark source as visited inQueue[src] = true; while (!q.isEmpty()) { // Front vertex of Queue int u = q.peek(); q.remove(); inQueue[u] = false; // Relaxing all edges of // vertex from the Queue for (pair x : g[u]) { int v = x.first; int cost = x.second; // Update the dist[v] to // minimum distance if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; // If vertex v is in Queue if (!inQueue[v]) { q.add(v); inQueue[v] = true; cnt[v]++; // Negative cycle if (cnt[v] >= V) return true; } } } } // No cycle found return false; } // Driver Code public static void main(String[] args) { // Number of vertices int N = 4; // Given source node src int src = 0; // Number of Edges int M = 4; // Given Edges with weight int Edges[][] = {{0, 1, 1}, {1, 2, -1}, {2, 3, -1}, {3, 0, -1}}; // If cycle is present if (sfpa(N, src, Edges, M) == true) System.out.print("Yes" + "\n"); else System.out.print("No" + "\n"); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach import sys def sfpa(V, src, Edges, M): # Stores the adjacency list of # the given graph g = [[] for i in range(V)] # Create Adjacency List for i in range(M): u = Edges[i][0] v = Edges[i][1] w = Edges[i][2] g[u].append([v, w]) # Stores the distance of all # reachable vertex from source dist = [sys.maxsize for i in range(V)] # Check if vertex is present # in queue or not inQueue = [False for i in range(V)] # Counts the relaxation for # each vertex cnt = [0 for i in range(V)] # Distance from src to src is 0 dist[src] = 0 # Create a queue q = [] # Push source in the queue q.append(src) # Mark source as visited inQueue[src] = True while (len(q)): # Front vertex of Queue u = q[0] q.remove(q[0]) inQueue[u] = False # Relaxing all edges of # vertex from the Queue for x in g[u]: v = x[0] cost = x[1] # Update the dist[v] to # minimum distance if (dist[v] > dist[u] + cost): dist[v] = dist[u] + cost # If vertex v is in Queue if (inQueue[v] == False): q.append(v) inQueue[v] = True cnt[v] += 1 # Negative cycle if (cnt[v] >= V): return True # No cycle found return False # Driver Code if __name__ == '__main__': # Number of vertices N = 4 # Given source node src src = 0 # Number of Edges M = 4 # Given Edges with weight Edges = [ [ 0, 1, 1 ], [ 1, 2, -1 ], [ 2, 3, -1 ], [ 3, 0, -1 ] ] # If cycle is present if (sfpa(N, src, Edges, M) == True): print("Yes") else: print("No") # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } static bool sfpa(int V, int src, int [,]Edges, int M) { // Stores the adjacency list of // the given graph List<pair> []g = new List<pair>[V]; for (int i = 0; i < V; i++) { g[i] = new List<pair>(); } // Create Adjacency List for (int i = 0; i < M; i++) { int u = Edges[i, 0]; int v = Edges[i, 1]; int w = Edges[i, 2]; g[u].Add(new pair(v, w)); } // Stores the distance of all // reachable vertex from source int []dist = new int[V]; for (int i = 0; i < V; i++) dist[i] = int.MaxValue; // Check if vertex is present // in queue or not bool []inQueue = new bool[V]; // Counts the relaxation for // each vertex int []cnt = new int[V]; // Distance from src // to src is 0 dist[src] = 0; // Create a queue Queue<int> q = new Queue<int>(); // Push source in the queue q.Enqueue(src); // Mark source as visited inQueue[src] = true; while (q.Count != 0) { // Front vertex of Queue int u = q.Peek(); q.Dequeue(); inQueue[u] = false; // Relaxing all edges of // vertex from the Queue foreach (pair x in g[u]) { int v = x.first; int cost = x.second; // Update the dist[v] to // minimum distance if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; // If vertex v is in Queue if (!inQueue[v]) { q.Enqueue(v); inQueue[v] = true; cnt[v]++; // Negative cycle if (cnt[v] >= V) return true; } } } } // No cycle found return false; } // Driver Code public static void Main(String[] args) { // Number of vertices int N = 4; // Given source node src int src = 0; // Number of Edges int M = 4; // Given Edges with weight int [,]Edges = {{0, 1, 1}, {1, 2, -1}, {2, 3, -1}, {3, 0, -1}}; // If cycle is present if (sfpa(N, src, Edges, M) == true) Console.Write("Yes" + "\n"); else Console.Write("No" + "\n"); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program for // the above approach class pair { constructor(first, second) { this.first = first; this.second = second; } } function sfpa(V, src, Edges, M) { // Stores the adjacency list of // the given graph var g = Array.from(Array(V), ()=>Array()); // Create Adjacency List for(var i = 0; i < M; i++) { var u = Edges[i][0]; var v = Edges[i][1]; var w = Edges[i][2]; g[u].push(new pair(v, w)); } // Stores the distance of all // reachable vertex from source var dist = Array(V); for (var i = 0; i < V; i++) dist[i] = 1000000000; // Check if vertex is present // in queue or not var inQueue = Array(V).fill(false); // Counts the relaxation for // each vertex var cnt = Array(V).fill(0); // Distance from src // to src is 0 dist[src] = 0; // Create a queue var q = []; // Push source in the queue q.push(src); // Mark source as visited inQueue[src] = true; while (q.length != 0) { // Front vertex of Queue var u = q[0]; q.shift(); inQueue[u] = false; // Relaxing all edges of // vertex from the Queue for(var x of g[u]) { var v = x.first; var cost = x.second; // Update the dist[v] to // minimum distance if (dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; // If vertex v is in Queue if (!inQueue[v]) { q.push(v); inQueue[v] = true; cnt[v]++; // Negative cycle if (cnt[v] >= V) return true; } } } } // No cycle found return false; } // Driver Code // Number of vertices var N = 4; // Given source node src var src = 0; // Number of Edges var M = 4; // Given Edges with weight var Edges = [[0, 1, 1], [1, 2, -1], [2, 3, -1], [3, 0, -1]]; // If cycle is present if (sfpa(N, src, Edges, M) == true) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); </script>
Yes
Complejidad temporal: O(N*M), donde N es el número de vértices y M es el número de aristas.
Espacio Auxiliar: O(N + M)
Publicación traducida automáticamente
Artículo escrito por elitecoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA