Ruta desde una fuente dada a un destino dado que tiene el K-ésimo peso más grande en un Gráfico

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:

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)

Publicación traducida automáticamente

Artículo escrito por avaies y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *