Path from a given source to a given destination having Kth largest weight in a Graph

  

import java.io.*;

import java.util.*;

  

class Edge {

  

    

    int src;

  

    

    int nbr;

  

    

    int wt;

  

    

    Edge(int src, int nbr, int wt)

    {

        this.src = src;

        this.nbr = nbr;

        this.wt = wt;

    }

}

  

class Pair implements Comparable<Pair> {

  

    

    int wsf;

  

    

    String psf;

  

    

    Pair(int wsf, String psf)

    {

        this.wsf = wsf;

        this.psf = psf;

    }

  

    

    

    public int compareTo(Pair o)

    {

        return this.wsf - o.wsf;

    }

}

  

class GFG {

  

    

    static PriorityQueue<Pair> pq

        = new PriorityQueue<>();

  

    

    

    public static void kthLargest(

        ArrayList<Edge>[] graph,

        int src, int dest,

        boolean[] visited, int k,

        String psf, int wsf)

    {

        

        

        if (src == dest) {

  

            

            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;

        }

  

        

        visited[src] = true;

  

        

        

        for (Edge e : graph[src]) {

  

            

            if (!visited[e.nbr]) {

  

                kthLargest(graph, e.nbr,

                           dest, visited,

                           k, psf + e.nbr,

                           wsf + e.wt);

            }

        }

  

        

        visited[src] = false;

    }

  

    

    public static void addEdges(

        ArrayList<Edge>[] graph)

    {

        

        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));

    }

  

    

    

    public static void kthLargestPathUtil(

        int N, int M, int src,

        int dest, int k)

    {

        @SuppressWarnings("unchecked")

  

        

        ArrayList<Edge>[] graph

            = new ArrayList[2 * N];

  

        for (int i = 0; i < 2 * N; i++) {

            graph[i] = new ArrayList<>();

        }

  

        

        addEdges(graph);

  

        

        boolean[] visited = new boolean[N];

  

        kthLargest(graph, src, dest,

                   visited, k, src + "",

                   0);

  

        

        String path = pq.peek().psf;

  

        

        for (int i = 0;

             i < path.length(); i++) {

            System.out.print(

                path.charAt(i) + " ");

        }

    }

  

    

    public static void main(String[] args)

    {

        

        int N = 7, M = 8;

  

        

        int src = 0;

  

        

        int dest = 6;

        int k = 3;

  

        kthLargestPathUtil(N, M, src,

                           dest, k);

    }

}

Let's block ads! (Why?)