Dado un grafo no dirigido que consta de N Nodes y M aristas, la tarea es encontrar la longitud mínima del camino desde el Node 1 al Node N pasando por todos los Nodes posibles del grafo dado. 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, bordes[][] = {{1, 2}, {2, 3}, {1, 3}, {2, 4}}
Salida: 2 2 3 2
Explicación:
Longitud de ruta mínima de 1 a 4, pasando de 1 es 2.
Longitud de ruta mínima de 1 a 4, pasando de 2 es 2.
Longitud de ruta mínima de 1 a 4, pasando de 3 es 3.
Longitud de ruta mínima de 1 a 4, pasando de 4 es 2.Entrada: N = 5, M = 7, bordes[][] = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {4, 3}, {4, 5}, {1, 5}}
Salida: 1 2 4 2 1
Enfoque: la idea es ejecutar 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. La suma de ambas distancias mínimas será la longitud mínima del camino de 1 a N incluyendo 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.
- Inicialice dos arrays , digamos dist1[] y dist2[] que almacenan la distancia más corta realizando BFS1 y BFS2 .
- 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 , entonces actualice dist[y] igual a dis + 1 .
- Después de llenar las dos arrays dist1[] y dist2[] en los pasos anteriores, itere sobre el rango [0, N] y si la suma de (dist1[i] + dist2[i]) es mayor que 10 9 , imprima “ -1” ya que no existe tal ruta. De lo contrario, imprima el valor de (dist1[i] + dist2[i]) como resultado.
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 minDisIncludingNode(int n, int m,
int edges[][2])
{
// Vector to store our edges
vector<ll> g[10005];
// Storing the edgees in the 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> > q;
q.push({ 0, 0 });
vector<int> dist(n, 1e9);
dist[0] = 0;
// BFS from first node using queue
while (!q.empty()) {
auto up = q.front();
// Pop from queue
q.pop();
int x = up.first;
int lev = up.second;
if (lev > dist[x])
continue;
if (x == n - 1)
continue;
// Traversing its adjacency list
for (ll y : g[x]) {
if (dist[y] > lev + 1) {
dist[y] = lev + 1;
q.push({ y, lev + 1 });
}
}
}
// Initialize queue
queue<pair<ll, ll> > q1;
q1.push({ n - 1, 0 });
vector<int> dist1(n, 1e9);
dist1[n - 1] = 0;
// BFS from last node using queue
while (!q1.empty()) {
auto up = q1.front();
// Pop from queue
q1.pop();
int x = up.first;
int lev = up.second;
if (lev > dist1[x])
continue;
if (x == 0)
continue;
// Traversing its adjacency list
for (ll y : g[x]) {
if (dist1[y] > lev + 1) {
dist1[y] = lev + 1;
q1.push({ y, lev + 1 });
}
}
}
// Printing the minimum distance
// including node i
for (int i = 0; i < n; i++) {
// If not reachable
if (dist[i] + dist1[i] > 1e9)
cout << -1 << " ";
// Path exists
else
cout << dist[i] + dist1[i] << " ";
}
}
// Driver Code
int main()
{
// Given Input
int n = 5;
int m = 7;
int edges[m][2]
= { { 1, 2 }, { 1, 4 },
{ 2, 3 }, { 2, 5 },
{ 4, 3 }, { 4, 5 },
{ 1, 5 } };
// Function Call
minDisIncludingNode(n, m, edges);
return 0;
}
Python3
# Python 3 program for the above approach # Function to calculate the distances # from node 1 to N def minDisIncludingNode(n, m, edges): # Vector to store our edges g = [[] for i in range(10005)] # Storing the edgees in the 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 q = [] q.append([0, 0]) dist = [1e9 for i in range(n)] dist[0] = 0 # BFS from first node using queue while(len(q)>0): up = q[0] # Pop from queue q = q[1:] x = up[0] lev = up[1] if (lev > dist[x]): continue if (x == n - 1): continue # Traversing its adjacency list for y in g[x]: if (dist[y] > lev + 1): dist[y] = lev + 1 q.append([y, lev + 1]) # Initialize queue q1 = [] q1.append([n - 1, 0]) dist1 = [1e9 for i in range(n)] dist1[n - 1] = 0 # BFS from last node using queue while (len(q1) > 0): up = q1[0] # Pop from queue q1 = q1[1:] x = up[0] lev = up[1] if (lev > dist1[x]): continue if (x == 0): continue # Traversing its adjacency list for y in g[x]: if (dist1[y] > lev + 1): dist1[y] = lev + 1 q1.append([y, lev + 1]) # Printing the minimum distance # including node i for i in range(n): # If not reachable if (dist[i] + dist1[i] > 1e9): print(-1,end = " ") # Path exists else: print(dist[i] + dist1[i],end = " ") # Driver Code if __name__ == '__main__': # Given Input n = 5 m = 7 edges = [[1, 2],[1, 4],[2, 3],[2, 5],[4, 3],[4, 5],[1, 5]] # Function Call minDisIncludingNode(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 minDisIncludingNode(n, m, edges) {
// Vector to store our edges
let g = new Array(10005).fill(0).map(() => []);
// Storing the edgees in the 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 q = [];
q.push([0, 0]);
dist = new Array(n).fill(1e9);
dist[0] = 0;
// BFS from first node using queue
while (q.length > 0) {
let up = q[0];
// Pop from queue
q.pop();
let x = up[0];
let lev = up[1];
if (lev > dist[x]) continue;
if (x == n - 1) continue;
// Traversing its adjacency list
for (let y of g[x]) {
if (dist[y] > lev + 1) {
dist[y] = lev + 1;
q.push([y, lev + 1]);
}
}
}
// Initialize queue
let q1 = [];
q1.push([n - 1, 0]);
let dist1 = new Array(n).fill(1e9);
dist1[n - 1] = 0;
// BFS from last node using queue
while (q1.length > 0) {
let up = q1[0];
// Pop from queue
q1.pop();
let x = up[0];
let lev = up[1];
if (lev > dist1[x]) continue;
if (x == 0) continue;
// Traversing its adjacency list
for (let y of g[x]) {
if (dist1[y] > lev + 1) {
dist1[y] = lev + 1;
q1.push([y, lev + 1]);
}
}
}
// Printing the minimum distance
// including node i
for (let i = 0; i < n; i++) {
// If not reachable
if (dist[i] + dist1[i] > 1e9) document.write(-1 + " ");
// Path exists
else document.write(dist[i] + dist1[i] + " ");
}
}
// Driver Code
// Given Input
let n = 5;
let m = 7;
let edges = [
[1, 2],
[1, 4],
[2, 3],
[2, 5],
[4, 3],
[4, 5],
[1, 5],
];
// Function Call
minDisIncludingNode(n, m, edges);
// This code is contributed by gfgking
</script>
Producción:
1 2 4 2 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