Dado un gráfico ponderado dirigido y dos vértices S y D en él, la tarea es encontrar el camino más corto de S a D con exactamente K aristas en el camino. Si no existe tal ruta, imprima -1.
Ejemplos:
Entrada: N = 3, K = 2, ed = {{{1, 2}, 5}, {{2, 3}, 3}, {{3, 1}, 4}}, S = 1, D = 3
Salida: 8
Explicación: El camino más corto con dos aristas será 1->2->3Entrada: N = 3, K = 4, ed = {{{1, 2}, 5}, {{2, 3}, 3}, {{3, 1}, 4}}, S = 1, D = 3
Salida: -1
Explicación: No existe ninguna ruta con longitud de borde 4 desde el Node 1 al 3Entrada: N = 3, K = 5, ed = {{{1, 2}, 5}, {{2, 3}, 3}, {{3, 1}, 4}}, S = 1, D = 3
Salida: 20
Explicación: La ruta más corta será 1->2->3->1->2->3.
Enfoque: Ya se discutió un enfoque O(V^3*K) para este problema en el artículo anterior. En este artículo, se analiza un enfoque O(E*K) para resolver este problema.
La idea es usar programación dinámica para resolver este problema.
Sea dp[X][J] el camino más corto desde el Node S al Node X usando exactamente J aristas en total. Usando esto, dp[X][J+1] se puede calcular como:
dp[X][J+1] = min(arr[Y][J]+weight[{Y, X}])
for all Y which has an edge from Y to X.
El resultado del problema se puede calcular siguiendo los pasos a continuación:
- Inicialice una array, dis[] con valor inicial como ‘inf’ excepto dis[S] como 0.
- Para i es igual a 1 – K, ejecute un bucle
- Inicialice una array, dis1[] con valor inicial como ‘inf’.
- Para cada arista del gráfico,
dis1[arista.segundo] = min(dis1[arista.segundo], dis[arista.primero]+peso(arista))
- 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 above approach
#include <bits/stdc++.h>
#define inf 100000000
using namespace std;
// Function to find the smallest path
// with exactly K edges
double smPath(int s, int d,
vector<pair<pair<int, int>, int> > ed,
int n, int k)
{
// Array to store dp
int dis[n + 1];
// Initialising the array
for (int i = 0; i <= n; i++)
dis[i] = inf;
dis[s] = 0;
// Loop to solve DP
for (int i = 0; i < k; i++) {
// Initialising next state
int dis1[n + 1];
for (int j = 0; j <= n; j++)
dis1[j] = inf;
// Recurrence relation
for (auto it : ed)
dis1[it.first.second] = min(dis1[it.first.second],
dis[it.first.first]
+ it.second);
for (int i = 0; i <= n; i++)
dis[i] = dis1[i];
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
int main()
{
int n = 4;
vector<pair<pair<int, int>, int> > ed;
// Input edges
ed = { { { 0, 1 }, 10 },
{ { 0, 2 }, 3 },
{ { 0, 3 }, 2 },
{ { 1, 3 }, 7 },
{ { 2, 3 }, 7 } };
// Source and Destination
int s = 0, d = 3;
// Number of edges in path
int k = 2;
// Calling the function
cout << smPath(s, d, ed, n, k);
}
Java
// Java implementation of the above approach
import java.util.ArrayList;
import java.util.Arrays;
class GFG{
static class Pair<K, V>
{
K first;
V second;
public Pair(K first, V second)
{
this.first = first;
this.second = second;
}
}
static int inf = 100000000;
// Function to find the smallest path
// with exactly K edges
static int smPath(int s, int d,
ArrayList<Pair<Pair<Integer, Integer>, Integer>> ed,
int n, int k)
{
// Array to store dp
int[] dis = new int[n + 1];
// Initialising the array
Arrays.fill(dis, inf);
dis[s] = 0;
// Loop to solve DP
for(int i = 0; i < k; i++)
{
// Initialising next state
int[] dis1 = new int[n + 1];
Arrays.fill(dis1, inf);
// Recurrence relation
for(Pair<Pair<Integer, Integer>, Integer> it : ed)
dis1[it.first.second] = Math.min(dis1[it.first.second],
dis[it.first.first] +
it.second);
for(int j = 0; j <= n; j++)
dis[j] = dis1[j];
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
public static void main(String[] args)
{
int n = 4;
// Input edges
ArrayList<Pair<Pair<Integer, Integer>, Integer>> ed = new ArrayList<>(
Arrays.asList(
new Pair<Pair<Integer, Integer>, Integer>(
new Pair<Integer, Integer>(0, 1), 10),
new Pair<Pair<Integer, Integer>, Integer>(
new Pair<Integer, Integer>(0, 2), 3),
new Pair<Pair<Integer, Integer>, Integer>(
new Pair<Integer, Integer>(0, 3), 2),
new Pair<Pair<Integer, Integer>, Integer>(
new Pair<Integer, Integer>(1, 3), 7),
new Pair<Pair<Integer, Integer>, Integer>(
new Pair<Integer, Integer>(2, 3), 7)
)
);
// Source and Destination
int s = 0, d = 3;
// Number of edges in path
int k = 2;
// Calling the function
System.out.println(smPath(s, d, ed, n, k));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation of the above approach inf = 100000000 # Function to find the smallest path # with exactly K edges def smPath(s, d, ed, n, k): # Array to store dp dis = [inf] * (n + 1) dis[s] = 0 # Loop to solve DP for i in range(k): # Initialising next state dis1 = [inf] * (n + 1) # Recurrence relation for it in ed: dis1[it[1]] = min(dis1[it[1]], dis[it[0]]+ it[2]) for i in range(n + 1): dis[i] = dis1[i] # Returning final answer if (dis[d] == inf): return -1 else: return dis[d] # Driver code if __name__ == '__main__': n = 4 # Input edges ed = [ [0, 1 ,10], [ 0, 2 ,3], [ 0, 3 ,2], [ 1, 3 ,7], [ 2, 3 ,7] ] # Source and Destination s = 0 d = 3 # Number of edges in path k = 2 # Calling the function print(smPath(s, d, ed, n, k)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG{
static int inf = 100000000;
// Function to find the smallest path
// with exactly K edges
public static int smPath(int s, int d,
List<KeyValuePair<KeyValuePair<int, int>, int>> ed,
int n, int k)
{
// Array to store dp
// Initialising the array
int []dis = Enumerable.Repeat(inf, n+1).ToArray();
dis[s] = 0;
// Loop to solve DP
for(int i = 0; i < k; i++)
{
// Initialising next state
int []dis1 = Enumerable.Repeat(inf, n+1).ToArray();
// Recurrence relation
foreach(KeyValuePair<KeyValuePair<int, int>, int> it in ed)
dis1[it.Key.Value] = Math.Min(dis1[it.Key.Value],
dis[it.Key.Key] +
it.Value);
for(int j = 0; j <= n; j++)
dis[j] = dis1[j];
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
public static void Main(string[] args)
{
int n = 4;
// Input edges
List<KeyValuePair<KeyValuePair<int, int>, int>> ed = new List<KeyValuePair<KeyValuePair<int, int>, int>>(){
new KeyValuePair<KeyValuePair<int, int>, int>(
new KeyValuePair<int, int>(0, 1), 10),
new KeyValuePair<KeyValuePair<int, int>, int>(
new KeyValuePair<int, int>(0, 2), 3),
new KeyValuePair<KeyValuePair<int, int>, int>(
new KeyValuePair<int, int>(0, 3), 2),
new KeyValuePair<KeyValuePair<int, int>, int>(
new KeyValuePair<int, int>(1, 3), 7),
new KeyValuePair<KeyValuePair<int, int>, int>(
new KeyValuePair<int, int>(2, 3), 7)
};
// Source and Destination
int s = 0, d = 3;
// Number of edges in path
int k = 2;
// Calling the function
Console.Write(smPath(s, d, ed, n, k));
}
}
// This code is contributed by rrrtnx.
Javascript
<script>
// Javascript implementation of the above approach
let inf = 100000000;
// Function to find the smallest path
// with exactly K edges
function smPath(s,d,ed,n,k)
{
// Array to store dp
let dis = new Array(n + 1);
// Initialising the array
for(let i=0;i<(n+1);i++)
{
dis[i]=inf;
}
dis[s] = 0;
// Loop to solve DP
for(let i = 0; i < k; i++)
{
// Initialising next state
let dis1 = new Array(n + 1);
for(let i=0;i<(n+1);i++)
{
dis1[i]=inf;
}
// Recurrence relation
for(let it=0;it< ed.length;it++)
dis1[ed[it][1]] = Math.min(dis1[ed[it][1]],
dis[ed[it][0]] +
ed[it][2]);
document.write()
for(let j = 0; j <= n; j++)
dis[j] = dis1[j];
}
// Returning final answer
if (dis[d] == inf)
return -1;
else
return dis[d];
}
// Driver code
let n = 4;
// Input edges
let ed = [ [0, 1 ,10],
[ 0, 2 ,3],
[ 0, 3 ,2],
[ 1, 3 ,7],
[ 2, 3 ,7] ];
// Source and Destination
let s = 0, d = 3;
// Number of edges in path
let k = 2;
// Calling the function
document.write(smPath(s, d, ed, n, k));
// This code is contributed by patel2127
</script>
Producción:
10
Complejidad temporal: O(E*K)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA