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

0 0 11 minutes read

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 K^th 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 3^rd 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 K^th 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 K^th 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 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);
    }
}

Python3

# Python program for the above approach
 
# Edge class represents a source,
# destination, weight of the edge
 
 
class Edge:
 
    # source
    def __init__(self, src, nbr, wt):
        self.src = src
        self.nbr = nbr
        self.wt = wt
 
# Pair class
 
 
class 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 graph
 
 
def 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 edges
 
 
def 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 weight
 
 
def 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 Code
if __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 edge
public 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 class
public 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 edge
class Edge {
  constructor(src, nbr, wt) {
    this.src = src;
    this.nbr = nbr;
    this.wt = wt;
  }
}
 
// Initializing the priority queue
let 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 graph
function 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 edges
function 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 weight
function 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 Code
let N = 7,
  M = 8;
 
// Source vertex
let src = 0;
 
// Destination vertex
let 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 zambiatek!