Given a weighted graph consisting of N nodes and M edges, a source vertex, a destination vertex, and an integer K, the task is to find the path with Kth largest weight from source to destination in the graph.
Examples:
Input: N = 7, M = 8, source = 0, destination = 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}}
Output: 0 1 2 3 4 6
Explanation: A total of 4 paths exists from the source to the destination:
Path: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. Weight = 38.
Path: 0 ->1 -> 2 -> 3 -> 6. Weight = 40.
Path: 0 -> 3 -> 4 -> 5 -> 6. Weight = 48.
Path: 0 -> 3 -> 4 -> 6. Weight = 50.
The 3rd largest weighted path is the path with weight 40. Hence, the path having weight 40 is the output.Input: N = 2, M = 1, source = 0, destination = 1, K = 1, Edges[][] = {{0 1 25}},
Output: 0 1
Approach: The given problem can be solved by finding all the paths from a given source to a destination and using a Priority Queue to find the Kth largest weight. Follow the steps below to solve the problem:
- Initialize an adjacency list to create a graph from the given set of edges Edges[][].
- Initialize a Max-Heap using a priority queue, say PQ as a Min-Heap of size K, to store path weight and path as a string from source to destination.
- Initialize an array visited[], to mark if a vertex is visited or not.
- Traverse the graph to find all paths from source to destination.
- Create a utility class Pair as psf and wsf, for maintaining path and weight obtained so far respectively.
- In the priority queue, perform the following operations:
- If the queue has less than K elements, add the pair to the queue.
- Otherwise, if the current weight of the path is greater than the weight of the pair at the front of the queue, then remove the front element, and add the new pair to the queue.
- After completing the above steps, the element at the top of the priority queue gives the pair containing the Kth largest weight path. Therefore, print that path.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Edge class represents a source,// destination, weight of the edgeclass 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 queuepriority_queue<pair<int, string> > pq;// Function to find the path from src to// dest with Kth largest weight in the graphvoid 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 edgesvoid 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 weightvoid 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 Codeint 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 approachimport java.io.*;import java.util.*;// Edge class represents a source,// destination, weight of the edgeclass 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 classclass 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); }} |
Python3
# Python program for the above approach# Edge class represents a source,# destination, weight of the edgeclass Edge: # source def __init__(self, src, nbr, wt): self.src = src self.nbr = nbr self.wt = wt# Pair classclass Pair: # weight so far def __init__(self, wsf, psf): self.wsf = wsf self.psf = psf # Function to sort in increasing # order of weights def __cmp__(self, other): return self.wsf - other.wsf# Function to find the path from src# to dest with Kth largest weight in the graphdef kthLargest(graph, src, dest, visited, k, psf, wsf): # Base Case: When the # destination has been reached if src == dest: if len(pq) < k: pq.append(Pair(wsf, psf)) elif wsf > pq[0].wsf: pq.pop(0) pq.append(Pair(wsf, psf)) return # Mark the source node as visited visited[src] = True # Iterating over all # the neighbours of src for i in range(len(graph[src])): e = graph[src][i] if not visited[e.nbr]: kthLargest(graph, e.nbr, dest, visited, k, psf + str(e.nbr), wsf + e.wt) # Mark src as unvisited visited[src] = False# Function to add edgesdef addEdges(graph): # Adding a bidirectional edge graph[0].append(Edge(0, 1, 10)) graph[1].append(Edge(1, 0, 10)) graph[1].append(Edge(1, 2, 10)) graph[2].append(Edge(2, 1, 10)) graph[2].append(Edge(2, 3, 10)) graph[3].append(Edge(3, 2, 10)) graph[0].append(Edge(0, 3, 40)) graph[3].append(Edge(3, 0, 40)) graph[3].append(Edge(3, 4, 2)) graph[4].append(Edge(4, 3, 2)) graph[4].append(Edge(4, 5, 3)) graph[5].append(Edge(5, 4, 3)) graph[5].append(Edge(5, 6, 3)) graph[6].append(Edge(6, 5, 3)) graph[4].append(Edge(4, 6, 8)) graph[6].append(Edge(6, 4, 8))# Utility functionto find the# path with Kth largest weightdef kthLargestPathUtil(N, M, src, dest, k): # Arraylist to store edges graph = [[] for i in range(2 * N)] # Function to add edges addEdges(graph) # Stores if a vertex is visited or not visited = [False] * N # Stores the kth largest weighted path global pq pq = [] kthLargest(graph, src, dest, visited, k, str(src), 0) # Traversing path string print(pq[0].psf)# Driver Codeif __name__ == '__main__': # No of vertices and Edges N = 7 M = 8 # Source vertex src = 0 # Destination vertex dest = 6 k = 3 # Function call kthLargestPathUtil(N, M, src, dest, k) |
C#
using System;using System.Collections.Generic;// Edge class represents a source,// destination, weight of the edgepublic class Edge{ // Source public int src; // Destination public int nbr; // Weight public int wt; // Constructor to create an Edge public Edge(int src, int nbr, int wt) { this.src = src; this.nbr = nbr; this.wt = wt; }}// Pair classpublic class Pair : IComparable<Pair>{ // Weight so far public int wsf; // Path so for public string psf; // Constructor to create a Pair public 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; }}public class GFG{ static SortedSet<Pair> pq = new SortedSet<Pair>( Comparer<Pair>.Create((p1, p2) => p1.wsf.CompareTo(p2.wsf))); // Function to find the path from src to // dest with Kth largest weight in the graph public static void kthLargest( List<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.Count < k) { pq.Add(new Pair(wsf, psf)); } else if (wsf > pq.Min.wsf) { pq.Remove(pq.Min); pq.Add(new Pair(wsf, psf)); } return; } // Mark the source node as visited visited[src] = true; // Iterating over all // the neighbours of src foreach (Edge e in 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(List<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) { // Arraylist to store edges List<Edge>[] graph = new List<Edge>[2 * N]; for (int i = 0; i < 2 * N; i++) { graph[i] = new List<Edge>(); } // Function to add edges addEdges(graph); bool[] visited = new bool[N]; kthLargest(graph, src, dest, visited, k, src + "", 0); // Stores the kth largest weighted path string path = pq.Min.psf; // Traversing path string foreach (char c in path) { Console.Write(c + " "); } }// Driver code public static void Main() { // No of vertices and Edges int N = 7, M = 8; // Source vertex int src = 0; // Destination int dest = 6; int k = 3; kthLargestPathUtil(N, M, src, dest, k); }} |
Javascript
// Javascript code addition// Edge class represents a source,// destination, weight of the edgeclass Edge { constructor(src, nbr, wt) { this.src = src; this.nbr = nbr; this.wt = wt; }}// Initializing the priority queuelet pq = [];let x = 5;for (let i = 0; i < 3; i++) process.stdout.write(i + " ");// Function to find the path from src to// dest with Kth largest weight in the graphfunction kthLargest(graph, src, dest, visited, k, psf, wsf) { // Base Case: When the // destination has been reached if (src == dest) { // If pq has at most K elements if (pq.length < k) { pq.push([-wsf, psf]); } else if (-wsf > pq[0][0]) { pq.shift(); pq.push([-wsf, psf]); } return; } // Mark the source node as visited visited[src] = true; // Iterating over all // the neighbours of src for (let e of graph[src]) { // If neighbour is not visited if (!visited[e.nbr]) { kthLargest( graph, e.nbr, dest, visited, k, psf + e.nbr.toString(), wsf + e.wt ); } } // Mark src as unvisited visited[src] = false;}// Function to add edgesfunction addEdges(graph) { // creating edges let ob1 = new Edge(0, 1, 10); let ob2 = new Edge(1, 0, 10); let ob3 = new Edge(1, 2, 10); let ob4 = new Edge(1, 2, 10); let ob5 = new Edge(2, 3, 10); let ob6 = new Edge(3, 2, 10); let ob7 = new Edge(0, 3, 40); let ob8 = new Edge(3, 0, 40); let ob9 = new Edge(3, 4, 2); let ob10 = new Edge(4, 3, 2); let ob11 = new Edge(4, 5, 3); let ob12 = new Edge(5, 4, 3); let ob13 = new Edge(5, 6, 3); let ob14 = new Edge(6, 5, 3); let ob15 = new Edge(4, 6, 8); let ob16 = new Edge(6, 4, 8); // adding edges to the graph graph[0].push(ob1); graph[1].push(ob2); graph[1].push(ob3); graph[2].push(ob4); graph[2].push(ob5); graph[3].push(ob6); graph[0].push(ob7); graph[3].push(ob8); graph[3].push(ob9); graph[4].push(ob10); graph[4].push(ob11); graph[5].push(ob12); graph[5].push(ob13); graph[6].push(ob14); graph[4].push(ob15); graph[6].push(ob16);}// Utility function to find the// path with Kth largest weightfunction kthLargestPathUtil(N, M, src, dest, k) { // Array to store edges let graph = new Array(2 * N).fill().map(() => []); // Function to add edges addEdges(graph); // Stores if a vertex is visited or not let visited = new Array(N).fill(false); kthLargest(graph, src, dest, visited, k, src.toString(), 0); // Stores the kth largest weighted path let path = pq[pq.length - 1][1]; // Traversing path string for (let i = 1; i < path.length; i++) { if (path[i] == x) continue; process.stdout.write(path[i] + " "); }}// Driver Codelet N = 7, M = 8;// Source vertexlet src = 0;// Destination vertexlet dest = 6;let k = 3;kthLargestPathUtil(N, M, src, dest, k);// The code is contributed by Arushi Goel. |
Output
0 1 2 3 4 6
Time Complexity: O(V + E)
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
