Dado un gráfico no dirigido y no ponderado de N Nodes y M aristas, la tarea es contar las rutas de longitud mínima entre el Node 1 y N a través de cada uno de los Nodes. Si no existe tal ruta, imprima «-1» .
Nota: La ruta puede pasar por un Node cualquier número de veces.
Ejemplos:
Entrada: N = 4, M= 4, aristas = {{1, 2}, {2, 3}, {1, 3}, {2, 4}}
Salida: 1 1 1 1
Explicación:
Rutas totales de longitud mínima de 1 a 4, pasando de 1 es 1.
Rutas totales de longitud mínima de 1 a 4, pasando de 2 es 1.
Rutas totales de longitud mínima de 1 a 4, pasando de 3 es 1.
Rutas totales de longitud mínima de 1 a 4, pasando de 4 es 1.Entrada: N = 5, M = 5, aristas = {{1, 2}, {1, 4}, {1 3}, {2, 5}, {2, 4}}
Salida: 1 1 0 1 1
Enfoque: el problema dado se puede resolver realizando dos BFS , uno desde el Node 1 excluyendo el Node N y otro desde el Node N excluyendo el Node 1 para encontrar la distancia mínima de todos los Nodes desde 1 y N , y el producto de ambas distancias mínimas será el recuento total de caminos de longitud mínima de 1 a N , incluido el Node. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola , diga cola1 para realizar BFS desde el Node 1 y una cola cola2 para realizar BFS desde el Node N.
- Inicializa arrays , di dist[] para almacenar la distancia más corta yways[] para contar el número de formas de llegar a ese Node.
- Realice dos BFS y realice los siguientes pasos en cada caso:
- Salga de la cola y almacene el Node en x y su distancia en dis .
- Si dist[x] es más pequeño que dis entonces continúa .
- Recorra la lista de adyacencia de x y para cada hijo y , si dist[y] es mayor que dis + 1 , actualice dist[y] igual a dis + 1 yways[ y ] igual aways[x] . De lo contrario, si dist[y] es igual a dis +1 , agregueways[x] toways [y] .
- Finalmente, itere sobre el rango N y para cada Node imprima el recuento de rutas de longitud mínima comoways1[i]*ways2[i] .
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;
#define ll long long int
// Function to calculate the distances
// from node 1 to N
void countMinDistance(int n, int m,
int edges[][2])
{
// Stores the number of edges
vector<ll> g[10005];
// Storing the edges in vector
for (int i = 0; i < m; i++) {
int a = edges[i][0] - 1;
int b = edges[i][1] - 1;
g[a].push_back(b);
g[b].push_back(a);
}
// Initialize queue
queue<pair<ll, ll> > queue1;
queue1.push({ 0, 0 });
vector<int> dist(n, 1e9);
vector<int> ways1(n, 0);
dist[0] = 0;
ways1[0] = 1;
// BFS from 1st node using queue
while (!queue1.empty()) {
auto up = queue1.front();
// Pop from queue
queue1.pop();
int x = up.first;
int dis = up.second;
if (dis > dist[x])
continue;
if (x == n - 1)
continue;
// Traversing the adjacency list
for (ll y : g[x]) {
if (dist[y] > dis + 1) {
dist[y] = dis + 1;
ways1[y] = ways1[x];
queue1.push({ y, dis + 1 });
}
else if (dist[y] == dis + 1) {
ways1[y] += ways1[x];
}
}
}
// Initialize queue
queue<pair<ll, ll> > queue2;
queue2.push({ n - 1, 0 });
vector<int> dist1(n, 1e9);
vector<int> ways2(n, 0);
dist1[n - 1] = 0;
ways2[n - 1] = 1;
// BFS from last node
while (!queue2.empty()) {
auto up = queue2.front();
// Pop from queue
queue2.pop();
int x = up.first;
int dis = up.second;
if (dis > dist1[x])
continue;
if (x == 0)
continue;
// Traverse the adjacency list
for (ll y : g[x]) {
if (dist1[y] > dis + 1) {
dist1[y] = dis + 1;
ways2[y] = ways2[x];
queue2.push({ y, dis + 1 });
}
else if (dist1[y] == 1 + dis) {
ways2[y] += ways2[x];
}
}
}
// Print the count of minimum
// distance
for (int i = 0; i < n; i++) {
cout << ways1[i] * ways2[i] << " ";
}
}
// Driver Code
int main()
{
int N = 5, M = 5;
int edges[M][2] = {
{ 1, 2 }, { 1, 4 }, { 1, 3 },
{ 2, 5 }, { 2, 4 }
};
countMinDistance(N, M, edges);
return 0;
}
Python3
# Python 3 program for the above approach # Function to calculate the distances # from node 1 to N def countMinDistance(n, m, edges): # Stores the number of edges g = [[] for i in range(10005)] # Storing the edges in vector for i in range(m): a = edges[i][0] - 1 b = edges[i][1] - 1 g[a].append(b) g[b].append(a) # Initialize queue queue1 = [] queue1.append([0, 0]) dist = [1e9 for i in range(n)] ways1 = [0 for i in range(n)] dist[0] = 0 ways1[0] = 1 # BFS from 1st node using queue while (len(queue1)>0): up = queue1[0] # Pop from queue queue1 = queue1[:-1] x = up[0] dis = up[1] if (dis > dist[x]): continue if (x == n - 1): continue # Traversing the adjacency list for y in g[x]: if (dist[y] > dis + 1): dist[y] = dis + 1 ways1[y] = ways1[x] queue1.append([y, dis + 1]) elif(dist[y] == dis + 1): ways1[y] += ways1[x] # Initialize queue queue2 = [] queue2.append([n - 1, 0]) dist1 = [1e9 for i in range(n)] ways2 = [0 for i in range(n)] dist1[n - 1] = 0 ways2[n - 1] = 1 # BFS from last node while(len(queue2)>0): up = queue2[0] # Pop from queue queue2 = queue2[:-1] x = up[0] dis = up[1] if (dis > dist1[x]): continue if (x == 0): continue # Traverse the adjacency list for y in g[x]: if (dist1[y] > dis + 1): dist1[y] = dis + 1 ways2[y] = ways2[x] queue2.append([y, dis + 1]) elif(dist1[y] == 1 + dis): ways2[y] += ways2[x] # Print the count of minimum # distance ways1[n-1] = 1 ways2[n-1] = 1 for i in range(n): print(ways1[i] * ways2[i],end = " ") # Driver Code if __name__ == '__main__': N = 5 M = 5 edges = [[1, 2],[1, 4],[1, 3],[2, 5],[2, 4]] countMinDistance(N, M, edges) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to calculate the distances
// from node 1 to N
function countMinDistance(n, m, edges) {
// Stores the number of edges
let g = new Array(10005).fill(0).map(() => []);
// Storing the edges in vector
for (let i = 0; i < m; i++) {
let a = edges[i][0] - 1;
let b = edges[i][1] - 1;
g[a].push(b);
g[b].push(a);
}
// Initialize queue
let queue1 = [];
queue1.push([0, 0]);
let dist = new Array(n).fill(1e9);
let ways1 = new Array(n).fill(0);
dist[0] = 0;
ways1[0] = 1;
// BFS from 1st node using queue
while (queue1.length > 0) {
let up = queue1[0];
// Pop from queue
queue1.pop();
let x = up[0];
let dis = up[1];
if (dis > dist[x]) continue;
if (x == n - 1) continue;
// Traversing the adjacency list
for (let y of g[x]) {
if (dist[y] > dis + 1) {
dist[y] = dis + 1;
ways1[y] = ways1[x];
queue1.push([y, dis + 1]);
} else if (dist[y] == dis + 1) ways1[y] += ways1[x];
}
}
// Initialize queue
let queue2 = [];
queue2.push([n - 1, 0]);
let dist1 = new Array(n).fill(1e9);
let ways2 = new Array(n).fill(0);
dist1[n - 1] = 0;
ways2[n - 1] = 1;
// BFS from last node
while (queue2.length > 0) {
let up = queue2[0];
// Pop from queue
queue2.pop();
let x = up[0];
let dis = up[1];
if (dis > dist1[x]) continue;
if (x == 0) continue;
// Traverse the adjacency list
for (let y of g[x]) {
if (dist1[y] > dis + 1) {
dist1[y] = dis + 1;
ways2[y] = ways2[x];
queue2.push([y, dis + 1]);
} else if (dist1[y] == 1 + dis) ways2[y] += ways2[x];
}
}
// Print the count of minimum
// distance
ways1[n - 1] = 1;
ways2[n - 1] = 1;
for (let i = 0; i < n; i++) document.write(ways1[i] * ways2[i] + " ");
}
// Driver Code
let N = 5;
let M = 5;
let edges = [
[1, 2],
[1, 4],
[1, 3],
[2, 5],
[2, 4],
];
countMinDistance(N, M, edges);
// This code is contributed by gfgking
</script>
Producción:
1 1 0 1 1
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA