Dado un grafo ponderado que consta de N Nodes y M aristas, un vértice de origen , un vértice de destino y un número entero K , la tarea es encontrar la ruta con el K -ésimo peso más grande desde el origen hasta el destino en el gráfico.
Ejemplos:
Entrada: N = 7, M = 8, fuente = 0, destino = 6, K = 3, Edges[][] = {{0, 1, 10}, {1, 2, 10}, {2, 3, 10}, {0, 3, 40}, {3, 4, 2}, {4, 5, 3}, {5, 6, 3}, {4, 6, 8}, {2, 5, 5} }
Salida: 0 1 2 3 4 6
Explicación: Existe un total de 4 rutas desde el origen hasta el destino:
Ruta: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. Peso = 38.
Ruta: 0 ->1 -> 2 -> 3 -> 6. Peso = 40.
Ruta: 0 -> 3 -> 4 -> 5 -> 6. Peso = 48.
Ruta: 0 -> 3 -> 4 – > 6. Peso = 50.
La tercera ruta ponderada más grande es la ruta con un peso de 40. Por lo tanto, la ruta con un peso de 40 es la salida.Entrada: N = 2, M = 1, fuente = 0, destino = 1, K = 1, Edges[][] = {{0 1 25}},
Salida: 0 1
Enfoque: El problema dado se puede resolver encontrando todos los caminos desde una fuente dada hasta un destino y usando una Cola de Prioridad para encontrar el K -ésimo peso más grande . Siga los pasos a continuación para resolver el problema:
- Inicialice una lista de adyacencia para crear un gráfico a partir del conjunto dado de bordes Edges[][] .
- Inicialice un Max-Heap usando una cola de prioridad , digamos PQ como un Min-Heap de tamaño K , para almacenar el peso de la ruta y la ruta como una string desde el origen hasta el destino.
- Inicializar una array visited[] , para marcar si un vértice es visitado o no.
- Recorra el gráfico para encontrar todos los caminos desde el origen hasta el destino .
- Cree un Par de clase de utilidad como psf y wsf , para mantener la ruta y el peso obtenidos hasta ahora, respectivamente.
- En la cola de prioridad, realice las siguientes operaciones:
- Si la cola tiene menos de K elementos, agregue el par a la cola .
- De lo contrario, si el peso actual de la ruta es mayor que el peso del par al principio de la cola, elimine el elemento delantero y agregue el nuevo par a la cola.
- Después de completar los pasos anteriores, el elemento en la parte superior de la cola de prioridad proporciona el par que contiene la K -ésima ruta de mayor peso. Por lo tanto, imprima esa ruta.
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;
// Edge class represents a source,
// destination, weight of the edge
class Edge {
public:
// Source
int src;
// Destination
int nbr;
// Weight
int wt;
// Constructor to create an Edge
Edge(int srcc, int nbrr, int wtt)
{
src = srcc;
nbr = nbrr;
wt = wtt;
}
};
// Initializing the priority queue
priority_queue<pair<int, string> > pq;
// Function to find the path from src to
// dest with Kth largest weight in the graph
void kthLargest(vector<Edge> graph[], int src, int dest,
bool visited[], int k, string psf, int wsf)
{
// Base Case: When the
// destination has been reached
if (src == dest) {
// If pq has at most K elements
if (pq.size() < k) {
pq.push({ -wsf, psf });
}
else if (-wsf > pq.top().first) {
pq.pop();
pq.push({ -wsf, psf });
}
return;
}
// Mark the source node as visited
visited[src] = true;
// Iterating over all
// the neighbours of src
for (Edge e : graph[src]) {
// If neighbour is not visited
if (!visited[e.nbr]) {
kthLargest(graph, e.nbr, dest, visited, k,
psf + to_string(e.nbr), wsf + e.wt);
}
}
// Mark src as unvisited
visited[src] = false;
}
// Function to add edges
void addEdges(vector<Edge> graph[])
{
// creating edges
Edge ob1(0, 1, 10);
Edge ob2(1, 0, 10);
Edge ob3(1, 2, 10);
Edge ob4(1, 2, 10);
Edge ob5(2, 3, 10);
Edge ob6(3, 2, 10);
Edge ob7(0, 3, 40);
Edge ob8(3, 0, 40);
Edge ob9(3, 4, 2);
Edge ob10(4, 3, 2);
Edge ob11(4, 5, 3);
Edge ob12(5, 4, 3);
Edge ob13(5, 6, 3);
Edge ob14(6, 5, 3);
Edge ob15(4, 6, 8);
Edge ob16(6, 4, 8);
// adding edges to the graph
graph[0].push_back(ob1);
graph[1].push_back(ob2);
graph[1].push_back(ob3);
graph[2].push_back(ob4);
graph[2].push_back(ob5);
graph[3].push_back(ob6);
graph[0].push_back(ob7);
graph[3].push_back(ob8);
graph[3].push_back(ob9);
graph[4].push_back(ob10);
graph[4].push_back(ob11);
graph[5].push_back(ob12);
graph[5].push_back(ob13);
graph[6].push_back(ob14);
graph[4].push_back(ob15);
graph[6].push_back(ob16);
}
// Utility function to find the
// path with Kth largest weight
void kthLargestPathUtil(int N, int M, int src, int dest,
int k)
{
// Array to store edges
vector<Edge> graph[2 * N];
// Function to add edges
addEdges(graph);
// Stores if a vertex is visited or not
bool visited[N];
kthLargest(graph, src, dest, visited, k, src + "", 0);
// Stores the kth largest weighted path
string path = pq.top().second;
// Traversing path string
for (int i = 0; i < path.length(); i++) {
cout << path[i] << " ";
}
}
// Driver Code
int main()
{
// No of vertices and Edges
int N = 7, M = 8;
// Source vertex
int src = 0;
// Destination vertex
int dest = 6;
int k = 3;
kthLargestPathUtil(N, M, src, dest, k);
}
// This code is contributed by rj13to.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// Edge class represents a source,
// destination, weight of the edge
class Edge {
// Source
int src;
// Destination
int nbr;
// Weight
int wt;
// Constructor to create an Edge
Edge(int src, int nbr, int wt)
{
this.src = src;
this.nbr = nbr;
this.wt = wt;
}
}
// Pair class
class Pair implements Comparable<Pair> {
// Weight so far
int wsf;
// Path so far
String psf;
// Constructor to create a Pair
Pair(int wsf, String psf)
{
this.wsf = wsf;
this.psf = psf;
}
// Function to sort in increasing
// order of weights
public int compareTo(Pair o)
{
return this.wsf - o.wsf;
}
}
class GFG {
// Initializing the priority queue
static PriorityQueue<Pair> pq
= new PriorityQueue<>();
// Function to find the path from src to
// dest with Kth largest weight in the graph
public static void kthLargest(
ArrayList<Edge>[] graph,
int src, int dest,
boolean[] visited, int k,
String psf, int wsf)
{
// Base Case: When the
// destination has been reached
if (src == dest) {
// If pq has at most K elements
if (pq.size() < k) {
pq.add(new Pair(wsf, psf));
}
else if (wsf > pq.peek().wsf) {
pq.remove();
pq.add(new Pair(wsf, psf));
}
return;
}
// Mark the source node as visited
visited[src] = true;
// Iterating over all
// the neighbours of src
for (Edge e : graph[src]) {
// If neighbour is not visited
if (!visited[e.nbr]) {
kthLargest(graph, e.nbr,
dest, visited,
k, psf + e.nbr,
wsf + e.wt);
}
}
// Mark src as unvisited
visited[src] = false;
}
// Function to add edges
public static void addEdges(
ArrayList<Edge>[] graph)
{
// Adding a bidirectional edge
graph[0].add(new Edge(0, 1, 10));
graph[1].add(new Edge(1, 0, 10));
graph[1].add(new Edge(1, 2, 10));
graph[2].add(new Edge(2, 1, 10));
graph[2].add(new Edge(2, 3, 10));
graph[3].add(new Edge(3, 2, 10));
graph[0].add(new Edge(0, 3, 40));
graph[3].add(new Edge(3, 0, 40));
graph[3].add(new Edge(3, 4, 2));
graph[4].add(new Edge(4, 3, 2));
graph[4].add(new Edge(4, 5, 3));
graph[5].add(new Edge(5, 4, 3));
graph[5].add(new Edge(5, 6, 3));
graph[6].add(new Edge(6, 5, 3));
graph[4].add(new Edge(4, 6, 8));
graph[6].add(new Edge(6, 4, 8));
}
// Utility function to find the
// path with Kth largest weight
public static void kthLargestPathUtil(
int N, int M, int src,
int dest, int k)
{
@SuppressWarnings("unchecked")
// Arraylist to store edges
ArrayList<Edge>[] graph
= new ArrayList[2 * N];
for (int i = 0; i < 2 * N; i++) {
graph[i] = new ArrayList<>();
}
// Function to add edges
addEdges(graph);
// Stores if a vertex is visited or not
boolean[] visited = new boolean[N];
kthLargest(graph, src, dest,
visited, k, src + "",
0);
// Stores the kth largest weighted path
String path = pq.peek().psf;
// Traversing path string
for (int i = 0;
i < path.length(); i++) {
System.out.print(
path.charAt(i) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// No of vertices and Edges
int N = 7, M = 8;
// Source vertex
int src = 0;
// Destination vertex
int dest = 6;
int k = 3;
kthLargestPathUtil(N, M, src,
dest, k);
}
}
Complejidad Temporal: O(V + E)
Espacio Auxiliar: O(V)