Dado un Grafo Acíclico Dirigido con n vértices y m aristas. La tarea es encontrar el número de caminos diferentes que existen desde un vértice de origen hasta el vértice de destino.
Ejemplos:
Entrada: origen = 0, destino = 4
Salida: 3
Explicación:
0 -> 2 -> 3 -> 4
0 -> 3 -> 4
0 -> 4Entrada: fuente = 0, destino = 1
Salida: 1
Explicación: Solo existe una ruta 0->1
Enfoque: Sea f(u) el número de formas en que uno puede viajar desde el Node u hasta el vértice de destino . Por lo tanto, f (fuente) es una respuesta obligatoria. Como f (destino) = 1 aquí, solo hay un camino desde el destino hasta sí mismo. Se puede observar que f(u) no depende de nada más que de los valores f de todos los Nodes que son posibles de viajar desde u. Tiene sentido porque el número de caminos diferentes desde u hasta el destino es la suma de todos los caminos diferentes desde v1, v2, v3… vn hasta el vértice de destino donde v1 a vn son todos los vértices que tienen un camino directo desde el vértice u. Este enfoque, sin embargo, es demasiado lento para ser útil. Cada llamada de función se ramifica en más llamadas, y eso se ramifica en más llamadas, hasta que todas y cada una de las rutas se exploran una vez.
El problema con este enfoque es el cálculo de f(u) una y otra vez cada vez que se llama a la función con el argumento u. Dado que este problema exhibe tanto subproblemas superpuestos como una subestructura óptima , aquí se aplica la programación dinámica . Para evaluar f(u) para cada u solo una vez, evalúe f(v) para todos los v que se pueden visitar desde u antes de evaluar f(u). Esta condición se cumple mediante el orden clasificado topológico inverso de los Nodes del gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Number of paths
// from one vertex to another vertex
// in a Directed Acyclic Graph
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
// to make graph
vector<int> v[MAXN];
// function to add edge in graph
void add_edge(int a, int b, int fre[])
{
// there is path from a to b.
v[a].push_back(b);
fre[b]++;
}
// function to make topological sorting
vector<int> topological_sorting(int fre[], int n)
{
queue<int> q;
// insert all vertices which
// don't have any parent.
for (int i = 0; i < n; i++)
if (!fre[i])
q.push(i);
vector<int> l;
// using kahn's algorithm
// for topological sorting
while (!q.empty()) {
int u = q.front();
q.pop();
// insert front element of queue to vector
l.push_back(u);
// go through all it's childs
for (int i = 0; i < v[u].size(); i++) {
fre[v[u][i]]--;
// whenever the frequency is zero then add
// this vertex to queue.
if (!fre[v[u][i]])
q.push(v[u][i]);
}
}
return l;
}
// Function that returns the number of paths
int numberofPaths(int source, int destination, int n, int fre[])
{
// make topological sorting
vector<int> s = topological_sorting(fre, n);
// to store required answer.
int dp[n] = { 0 };
// answer from destination
// to destination is 1.
dp[destination] = 1;
// traverse in reverse order
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = 0; j < v[s[i]].size(); j++) {
dp[s[i]] += dp[v[s[i]][j]];
}
}
return dp;
}
// Driver code
int main()
{
// here vertices are numbered from 0 to n-1.
int n = 5;
int source = 0, destination = 4;
// to count number of vertex which don't
// have any parents.
int fre[n] = { 0 };
// to add all edges of graph
add_edge(0, 1, fre);
add_edge(0, 2, fre);
add_edge(0, 3, fre);
add_edge(0, 4, fre);
add_edge(2, 3, fre);
add_edge(3, 4, fre);
// Function that returns the number of paths
cout << numberofPaths(source, destination, n, fre);
}
Python3
# Python3 program for Number of paths # from one vertex to another vertex # in a Directed Acyclic Graph from collections import deque MAXN = 1000005 # to make graph v = [[] for i in range(MAXN)] # function to add edge in graph def add_edge(a, b, fre): # there is path from a to b. v[a].append(b) fre[b] += 1 # function to make topological sorting def topological_sorting(fre, n): q = deque() # insert all vertices which # don't have any parent. for i in range(n): if (not fre[i]): q.append(i) l = [] # using kahn's algorithm # for topological sorting while (len(q) > 0): u = q.popleft() #q.pop() # insert front element of queue to vector l.append(u) # go through all it's childs for i in range(len(v[u])): fre[v[u][i]] -= 1 # whenever the frequency is zero then add # this vertex to queue. if (not fre[v[u][i]]): q.append(v[u][i]) return l # Function that returns the number of paths def numberofPaths(source, destination, n, fre): # make topological sorting s = topological_sorting(fre, n) # to store required answer. dp = [0]*n # answer from destination # to destination is 1. dp[destination] = 1 # traverse in reverse order for i in range(len(s) - 1,-1,-1): for j in range(len(v[s[i]])): dp[s[i]] += dp[v[s[i]][j]] return dp # Driver code if __name__ == '__main__': # here vertices are numbered from 0 to n-1. n = 5 source, destination = 0, 4 # to count number of vertex which don't # have any parents. fre = [0]*n # to add all edges of graph add_edge(0, 1, fre) add_edge(0, 2, fre) add_edge(0, 3, fre) add_edge(0, 4, fre) add_edge(2, 3, fre) add_edge(3, 4, fre) # Function that returns the number of paths print (numberofPaths(source, destination, n, fre)) # This code is contributed by mohit kumar 29.
Java
// Java program for Number of paths
// from one vertex to another vertex
// in a Directed Acyclic Graph
import java.util.*;
class GFG{
static final int MAXN = 1000005;
// to make graph
static Vector<Integer> []v = new Vector[MAXN];
static {
for (int i = 0; i < v.length; i++)
v[i] = new Vector<Integer>();
}
// function to add edge in graph
static void add_edge(int a, int b, int fre[])
{
// there is path from a to b.
v[a].add(b);
fre[b]++;
}
// function to make topological sorting
static Vector<Integer> topological_sorting(int fre[], int n)
{
Queue<Integer> q = new LinkedList<Integer>();
// insert all vertices which
// don't have any parent.
for (int i = 0; i < n; i++)
if (fre[i]==0)
q.add(i);
Vector<Integer> l = new Vector<Integer>();
// using kahn's algorithm
// for topological sorting
while (!q.isEmpty()) {
int u = q.peek();
q.remove();
// insert front element of queue to vector
l.add(u);
// go through all it's childs
for (int i = 0; i < v[u].size(); i++) {
fre[v[u].get(i)]--;
// whenever the frequency is zero then add
// this vertex to queue.
if (fre[v[u].get(i)]==0)
q.add(v[u].get(i));
}
}
return l;
}
// Function that returns the number of paths
static int numberofPaths(int source, int destination, int n, int fre[])
{
// make topological sorting
Vector<Integer> s = topological_sorting(fre, n);
// to store required answer.
int dp[] = new int[n];
// answer from destination
// to destination is 1.
dp[destination] = 1;
// traverse in reverse order
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = 0; j < v[s.get(i)].size(); j++) {
dp[s.get(i)] += dp[v[s.get(i)].get(j)];
}
}
return dp;
}
// Driver code
public static void main(String[] args)
{
// here vertices are numbered from 0 to n-1.
int n = 5;
int source = 0, destination = 4;
// to count number of vertex which don't
// have any parents.
int fre[] = new int[n];
// to add all edges of graph
add_edge(0, 1, fre);
add_edge(0, 2, fre);
add_edge(0, 3, fre);
add_edge(0, 4, fre);
add_edge(2, 3, fre);
add_edge(3, 4, fre);
// Function that returns the number of paths
System.out.print(numberofPaths(source, destination, n, fre));
}
}
// This code contributed by shikhasingrajput
3
Método 2: (De arriba hacia abajo dp)
Consideremos el siguiente gráfico
Consideremos el origen como 0 ( cero ) y el destino como 4 . Ahora necesitamos encontrar el número de formas de llegar a 4 desde la fuente, es decir, 0. Una de las intuiciones básicas es que si ya estamos en el destino hemos encontrado 1 camino válido. Consideremos que nuestro origen y destino son diferentes a partir de ahora no sabemos de cuantas maneras podemos llegar de origen a destino. Pero si existen algunos vecinos para la fuente, entonces si los vecinos pueden llegar al destino a través de alguna ruta, entonces en todas estas rutas podemos agregar la fuente para obtener la cantidad de formas de llegar al destino desde la fuente.
Si podemos visualizarlo:
Para calcular el número de formas de llegar desde el origen al destino, es decir, del origen al destino. Si los vecinos de la fuente, es decir, 0, pueden llegar al destino (4) a través de alguna ruta, entonces podemos agregar la fuente para obtener la cantidad de formas en que la fuente puede llegar al destino.
fuente ( 0 ) vecinos son 4 , 3 , 2
4 es el destino, por lo que hemos encontrado 1 ruta válida. Entonces, para obtener la ruta desde la fuente, podemos agregar la fuente delante del destino, es decir, 0 -> 4.
El número de formas en que 3 puede llegar a 4 es 3 -> 4 es la única forma posible. En este caso, solo podemos agregar la fuente para obtener la cantidad de formas de llegar al destino desde la fuente a través de 3, es decir, 0 -> 3 -> 4. Este es un camino más posible.
El número de formas en que 2 puede llegar al 4 es 2 -> 3 -> 4 es la única forma posible. Ahora podemos agregar la fuente para obtener la ruta de la fuente al destino, es decir, 0 -> 2 -> 3 -> 4.
Hemos encontrado 3 formas posibles de llegar al destino desde el origen. Pero podemos ver que hay cierta superposición de subproblemas, es decir, cuando estamos calculando la respuesta para 2 estamos explorando el camino de 3 que ya hemos calculado. Para evitar esto, podemos simplemente almacenar el resultado de cada vértice en el que hemos calculado la respuesta, de modo que nos ayude a evitar calcular la solución de subproblemas similares una y otra vez. Ahí viene la intuición de la programación dinámica.
Acercarse :
- Si ya estamos en el destino, hemos encontrado una ruta válida.
- Si no hemos llegado al destino, entonces el número de formas de llegar al destino desde el vértice actual depende del número de formas en que los vecinos pueden llegar al destino. Sumamos todas las formas y las almacenamos en el arreglo dp.
- Si ya hemos calculado el resultado de cualquier vértice, devolvemos la respuesta directamente. Para identificar que no hemos calculado la respuesta para ningún vértice, inicializamos la array dp con -1 (indica que no hemos calculado la respuesta para ese vértice).
- Si los vecinos de algún vértice no pueden llegar al destino devolvemos -1 para indicar que no hay camino.
- Si el número de vías es realmente muy grande, podemos modularlo con 10^9 + 7 y almacenar el resultado.
A continuación se muestra la implementación de C++
C++
#include <bits/stdc++.h>
using namespace std;
long dp[10006];
long mod = 1e9 + 7;
/* function which returns the number
of ways to reach from source to destination */
long countPaths(vector<vector<long> >& arr, long s, long d)
{
/*
if we are already at the
destination we have found 1 valid
path
*/
if (s == d)
return 1;
/*
if we have already computed the
number of ways to reach the destination
via this vertex return the answer
*/
if (dp[s] != -1)
return dp[s];
long c = 0;
for (long& neigh : arr[s]) {
/*
since the number of ways to reach the
destination from the current vertex depends on
the number of ways the neighbours can reach the
destination so get all the possible ways that the
neighbours can reach the destination
*/
long x = countPaths(arr, neigh, d);
// if we reached the destination than add it to the
// result
if (x != -1) {
c = (c % mod + x % mod) % mod;
}
}
/*
if c is equal to zero that means there are no
paths from the current vertex to the destination so
return -1 to indicate there is no path or else store
the c and return it
*/
return (dp[s] = (c == 0) ? -1 : c);
}
long Possible_Paths(vector<vector<long> >& arr, long n,
long s, long d)
{
// initialise the dp array with -1
// to indicate we haven't computed
// the answer for any vertex
memset(dp, -1, sizeof dp);
long c = countPaths(arr, s, d);
// if there are no paths return 0
if (c == -1)
return 0;
// else return c
return c;
}
int main()
{
long n, m, s, d;
n = 5, m = 6, s = 0, d = 4;
vector<vector<long> > arr(n + 1);
arr[0].push_back(1);
arr[0].push_back(2);
arr[0].push_back(3);
arr[0].push_back(4);
arr[2].push_back(3);
arr[3].push_back(4);
cout << Possible_Paths(arr, n, s, d) << endl;
return 0;
}
3
Complejidad temporal: O (V+E) donde V son los vértices y E las aristas.
Complejidad espacial: O (V + E + V) donde O (V + E) para la lista de adyacencia y O (V) para la array dp.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA