Dado un grafo dirigido con N Nodes y E aristas donde el peso de cada arista es > 0 , dado también un origen S y un destino D . La tarea es encontrar el camino con el mínimo producto de aristas de S a D. Si no hay una ruta de S a D , imprima -1 .
Ejemplos:
Entrada: N = 3, E = 3, Bordes = {{{1, 2}, 0,5}, {{1, 3}, 1,9}, {{2, 3}, 3}}, S = 1 y D = 3
Salida: 1.5
Explicación:
El camino más corto será 1->2->3
con valor 0.5*3 = 1.5Entrada: N = 3, E = 3, Bordes = {{{1, 2}, 0,5}, {{2, 3}, 0,5}, {{3, 1}, 0,5}}, S = 1 y D = 3
Salida: ciclo detectado
Enfoque: La idea es utilizar el algoritmo Bellman Ford . Es porque el algoritmo de Dijkstra no se puede usar aquí, ya que solo funciona con bordes no negativos. Es porque al multiplicar valores entre [0-1), el producto sigue disminuyendo indefinidamente y finalmente se devuelve 0.
Además, es necesario detectar los ciclos porque si existe un ciclo, el producto de este ciclo disminuirá indefinidamente el producto a 0 y el producto tenderá a 0. Para simplificar, reportaremos tales ciclos.
Se pueden seguir los siguientes pasos para calcular el resultado:
- Inicialice una array, dis[] con valor inicial como ‘inf’ excepto dis[S] como 1.
- Ejecute un bucle desde 1 – N-1. Para cada borde en el gráfico:
- dis[borde.segundo] = min(dis[borde.segundo], dis[borde.primero]*peso(borde))
- Ejecute otro ciclo para cada borde en el gráfico, si algún borde sale con (des[borde.segundo] > dis[borde.primero]*peso(borde)), entonces se detecta el ciclo.
- Si dist[d] en infinito, devuelve -1 , de lo contrario, devuelve dist[d] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach.
#include <bits/stdc++.h>
using namespace std;
double inf = std::
numeric_limits<double>::infinity();
// Function to return the smallest
// product of edges
double bellman(int s, int d,
vector<pair<pair<int, int>,
double> >
ed,
int n)
{
// If the source is equal
// to the destination
if (s == d)
return 0;
// Array to store distances
double dis[n + 1];
// Initialising the array
for (int i = 1; i <= n; i++)
dis[i] = inf;
dis[s] = 1;
// Bellman ford algorithm
for (int i = 0; i < n - 1; i++)
for (auto it : ed)
dis[it.first.second] = min(dis[it.first.second],
dis[it.first.first]
* it.second);
// Loop to detect cycle
for (auto it : ed) {
if (dis[it.first.second]
> dis[it.first.first] * it.second)
return -2;
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
int main()
{
int n = 3;
vector<pair<pair<int, int>, double> > ed;
// Input edges
ed = { { { 1, 2 }, 0.5 },
{ { 1, 3 }, 1.9 },
{ { 2, 3 }, 3 } };
// Source and Destination
int s = 1, d = 3;
// Bellman ford
double get = bellman(s, d, ed, n);
if (get == -2)
cout << "Cycle Detected";
else
cout << get;
}
Java
// Java implementation of the approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
class Pair<K, V>
{
K first;
V second;
public Pair(K first, V second)
{
this.first = first;
this.second = second;
}
}
class GFG{
static final float inf = Float.POSITIVE_INFINITY;
// Function to return the smallest
// product of edges
static float bellman(int s, int d,
ArrayList<Pair<Pair<Integer,
Integer>, Float>> ed,
int n)
{
// If the source is equal
// to the destination
if (s == d)
return 0;
// Array to store distances
float[] dis = new float[n + 1];
// Initialising the array
Arrays.fill(dis, inf);
dis[s] = 1;
// Bellman ford algorithm
for(int i = 0; i < n - 1; i++)
for(Pair<Pair<Integer, Integer>, Float> it : ed)
dis[it.first.second] = Math.min(dis[it.first.second],
dis[it.first.first] *
it.second);
// Loop to detect cycle
for(Pair<Pair<Integer, Integer>, Float> it : ed)
{
if (dis[it.first.second] >
dis[it.first.first] *
it.second)
return -2;
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
public static void main(String[] args)
{
int n = 3;
// Input edges
ArrayList<Pair<Pair<Integer,
Integer>, Float>> ed = new ArrayList<>(
Arrays.asList(
new Pair<Pair<Integer, Integer>, Float>(
new Pair<Integer, Integer>(1, 2), 0.5f),
new Pair<Pair<Integer, Integer>, Float>(
new Pair<Integer, Integer>(1, 3), 1.9f),
new Pair<Pair<Integer, Integer>, Float>(
new Pair<Integer, Integer>(2, 3), 3f)));
// Source and Destination
int s = 1, d = 3;
// Bellman ford
float get = bellman(s, d, ed, n);
if (get == -2)
System.out.println("Cycle Detected");
else
System.out.println(get);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation of the approach.
import sys
inf = sys.maxsize;
# Function to return the smallest
# product of edges
def bellman(s, d, ed, n) :
# If the source is equal
# to the destination
if (s == d) :
return 0;
# Array to store distances
dis = [0]*(n + 1);
# Initialising the array
for i in range(1, n + 1) :
dis[i] = inf;
dis[s] = 1;
# Bellman ford algorithm
for i in range(n - 1) :
for it in ed :
dis[it[1]] = min(dis[it[1]], dis[it[0]] * ed[it]);
# Loop to detect cycle
for it in ed :
if (dis[it[1]] > dis[it[0]] * ed[it]) :
return -2;
# Returning final answer
if (dis[d] == inf) :
return -1;
else :
return dis[d];
# Driver code
if __name__ == "__main__" :
n = 3;
# Input edges
ed = { ( 1, 2 ) : 0.5 ,
( 1, 3 ) : 1.9 ,
( 2, 3 ) : 3 };
# Source and Destination
s = 1; d = 3;
# Bellman ford
get = bellman(s, d, ed, n);
if (get == -2) :
print("Cycle Detected");
else :
print(get);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG{
public static float inf = 1000000000;
// Function to return the smallest
// product of edges
public static float bellman(int s, int d,
List<KeyValuePair<KeyValuePair<int,
int>, float>> ed,
int n)
{
// If the source is equal
// to the destination
if (s == d)
return 0;
// Array to store distances
float[] dis = Enumerable.Repeat(inf, n+1).ToArray();
dis[s] = 1;
// Bellman ford algorithm
for(int i = 0; i < n - 1; i++)
foreach(KeyValuePair<KeyValuePair<int, int>, float> it in ed)
dis[it.Key.Value] = Math.Min(dis[it.Key.Value],
dis[it.Key.Key] *
it.Value);
// Loop to detect cycle
foreach(KeyValuePair<KeyValuePair<int, int>, float> it in ed)
{
if (dis[it.Key.Value] >
dis[it.Key.Key] *
it.Value)
return -2;
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
public static void Main(string[] args)
{
int n = 3;
// Input edges
List<KeyValuePair<KeyValuePair<int,
int>, float>> ed = new List<KeyValuePair<KeyValuePair<int,
int>, float>>(){
new KeyValuePair<KeyValuePair<int, int>, float>(
new KeyValuePair<int, int>(1, 2), 0.5f),
new KeyValuePair<KeyValuePair<int, int>, float>(
new KeyValuePair<int, int>(1, 3), 1.9f),
new KeyValuePair<KeyValuePair<int, int>, float>(
new KeyValuePair<int, int>(2, 3), 3f)};
// Source and Destination
int s = 1, d = 3;
// Bellman ford
float get = bellman(s, d, ed, n);
if (get == -2)
Console.Write("Cycle Detected");
else
Console.Write(get);
}
}
// This code is contributed by rrrtnx.
Javascript
<script>
// Javascript implementation of the approach.
var inf = 1000000000;
// Function to return the smallest
// product of edges
function bellman(s, d, ed, n)
{
// If the source is equal
// to the destination
if (s == d)
return 0;
// Array to store distances
var dis = Array(n+1).fill(inf);
dis[s] = 1;
// Bellman ford algorithm
for (var i = 0; i < n - 1; i++)
{
for(var j =0 ; j< ed.length; j++)
{
dis[ed[j][0][1]] = Math.min(dis[ed[j][0][1]],
dis[ed[j][0][0]]
* ed[j][1]);
}
}
// Loop to detect cycle
for (var it in ed) {
if (dis[it[0][1]]
> dis[it[0][0]] * it[1])
return -2;
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
var n = 3;
var ed;
// Input edges
ed = [ [ [ 1, 2 ], 0.5 ],
[ [ 1, 3 ], 1.9 ],
[ [ 2, 3 ], 3 ] ];
// Source and Destination
var s = 1, d = 3;
// Bellman ford
var get = bellman(s, d, ed, n);
if (get == -2)
document.write( "Cycle Detected");
else
document.write( get);
</script>
Producción:
1.5
Complejidad temporal: O(E*V)
Espacio auxiliar : O(V).
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA