Dado un gráfico ponderado dirigido que consta de N vértices y una array Edges[][] , donde cada fila representa dos vértices conectados por un borde y el peso de ese borde, la tarea es encontrar la ruta con la suma máxima de pesos de un vértice de origen dado src a un vértice de destino dado dst , formado por un máximo de K vértices intermedios. Si no existe tal ruta, imprima -1 .
Ejemplos:
Entrada: N = 3, Edges[][] = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, src = 0, dst = 2, K = 0
Salida : 500
Explicación:
Ruta 0 → 2: La ruta con peso máximo y como máximo 0 Nodes intermedios es de peso 500.
Entrada: N = 3, Edges[][] = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, src = 0, dst = 2, K = 0
Salida : 500
Explicación:
Camino 0 → 2: El camino con peso máximo y como máximo 1 Node intermedio es de peso 500.
Enfoque: el problema dado se puede resolver utilizando BFS (búsqueda primero en amplitud) transversal . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos ans , para almacenar la distancia máxima entre el origen y el Node de destino que tiene como máximo K Nodes intermedios.
- Inicialice una lista de adyacencia del gráfico usando los bordes.
- Inicialice una cola vacía e inserte el vértice de origen en ella . Inicialice una variable, digamos lvl , para almacenar la cantidad de Nodes presentes entre src y dst .
- Mientras la cola no esté vacía y el lvl sea menor que K + 2 , realice los siguientes pasos:
- Almacene el tamaño de la cola en una variable, digamos S .
- Iterar sobre el rango [1, S] y realizar los siguientes pasos:
- Extraiga el elemento frontal de la cola y guárdelo en una variable, digamos T .
- Si T es el vértice dst , actualice el valor de ans como el máximo de ans y la distancia actual T.segundo .
- Recorra todos los vecinos del Node emergente actual y verifique si la distancia de su vecino es mayor que la distancia actual o no. Si se encuentra que es cierto, entonces empújelo en la cola y actualice su distancia.
- Aumenta el valor de lvl en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como la distancia máxima resultante.
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;
// Function to find the longest distance
// from source to destination with at
// most K intermediate nodes
int findShortestPath(
int n, vector<vector<int> >& edges,
int src, int dst, int K)
{
// Initialize the adjacency list
vector<vector<pair<int, int> > > adjlist(
n, vector<pair<int, int> >());
// Initialize a queue to perform BFS
queue<pair<int, int> > q;
unordered_map<int, int> mp;
// Store the maximum distance of
// every node from source vertex
int ans = INT_MIN;
// Initialize adjacency list
for (int i = 0; i < edges.size(); i++) {
auto edge = edges[i];
adjlist[edge[0]].push_back(
make_pair(edge[1], edge[2]));
}
// Push the first element into queue
q.push({ src, 0 });
int level = 0;
// Iterate until the queue becomes empty
// and the number of nodes between src
// and dst vertex is at most to K
while (!q.empty() && level < K + 2) {
// Current size of the queue
int sz = q.size();
for (int i = 0; i < sz; i++) {
// Extract the front
// element of the queue
auto pr = q.front();
// Pop the front element
// of the queue
q.pop();
// If the dst vertex is reached
if (pr.first == dst)
ans = max(ans, pr.second);
// Traverse the adjacent nodes
for (auto pr2 : adjlist[pr.first]) {
// If the distance is greater
// than the current distance
if (mp.find(pr2.first)
== mp.end()
|| mp[pr2.first]
> pr.second
+ pr2.second) {
// Push it into the queue
q.push({ pr2.first,
pr.second
+ pr2.second });
mp[pr2.first] = pr.second
+ pr2.second;
}
}
}
// Increment the level by 1
level++;
}
// Finally, return the maximum distance
return ans != INT_MIN ? ans : -1;
}
// Driver Code
int main()
{
int n = 3, src = 0, dst = 2, k = 1;
vector<vector<int> > edges
= { { 0, 1, 100 },
{ 1, 2, 100 },
{ 0, 2, 500 } };
cout << findShortestPath(n, edges,
src, dst, k);
return 0;
}
Python3
# Python3 program for the above approach
from collections import deque
# Function to find the longest distance
# from source to destination with at
# most K intermediate nodes
def findShortestPath(n, edges, src, dst, K):
# Initialize the adjacency list
adjlist = [[] for i in range(n)]
# Initialize a queue to perform BFS
q = deque()
mp = {}
# Store the maximum distance of
# every node from source vertex
ans = -10**9
# Initialize adjacency list
for i in range(len(edges)):
edge = edges[i]
adjlist[edge[0]].append([edge[1],
edge[2]])
# Push the first element into queue
q.append([src, 0])
level = 0
# Iterate until the queue becomes empty
# and the number of nodes between src
# and dst vertex is at most to K
while (len(q) > 0 and level < K + 2):
# Current size of the queue
sz = len(q)
for i in range(sz):
# Extract the front
# element of the queue
pr = q.popleft()
# Pop the front element
# of the queue
# q.pop()
# If the dst vertex is reached
if (pr[0] == dst):
ans = max(ans, pr[1])
# Traverse the adjacent nodes
for pr2 in adjlist[pr[0]]:
# If the distance is greater
# than the current distance
if ((pr2[0] not in mp) or
mp[pr2[0]] > pr[1] + pr2[1]):
# Push it into the queue
q.append([pr2[0], pr[1] + pr2[1]])
mp[pr2[0]] = pr[1] + pr2[1]
# Increment the level by 1
level += 1
# Finally, return the maximum distance
return ans if ans != -10**9 else -1
# Driver Code
if __name__ == '__main__':
n, src, dst, k = 3, 0, 2, 1
edges= [ [ 0, 1, 100 ],
[ 1, 2, 100 ],
[ 0, 2, 500 ] ]
print(findShortestPath(n, edges,src, dst, k))
# This code is contributed by mohit kumar 29
500
Complejidad temporal: O(N + E)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rutvikchandla3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA