Minimum cost of path between given nodes containing at most K nodes in a directed and weighted graph

0 0 8 minutes read

Given a directed weighted graph represented by a 2-D array graph[][] of size n and 3 integers src, dst, and k representing the source point, destination point, and the available number of stops. The task is to minimize the cost of the path between two nodes containing at most K nodes in a directed and weighted graph. If there is no such route, return -1.

Examples:

Input: n=6, graph[][] = [[0, 1, 10], [1, 2, 20], [1, 3, 10], [2, 5, 30], [3, 4, 10], [4, 5, 10]], src=0, dst=5, k=2
Output: 60
Explanation:

Src = 0, Dst = 5 and k = 2

There can be a route marked with a green arrow that takes cost = 10+10+10+10=40 using three stops. And route marked with red arrow takes cost = 10+20+30=60 using two stops. But since there can be at most 2 stops, the answer will be 60.

Input: n=3, graph[][] = [[0, 1, 10], [0, 2, 50], [1, 2, 10], src=0, dst=2, k=1
Output: 20
Explanation:

Src=0 and Dst=2

Since the k is 1, then the green-colored path can be taken with a minimum cost of 20.

Approach: Increase k by 1 because on reaching the destination, k+1 stops will be consumed. Use Breadth-first search to run while loop till the queue becomes empty. At each time pop out all the elements from the queue and decrease k by 1 and check-in their adjacent list of elements and check they are not visited before or their cost is greater than the cost of parent node + cost of that node, then mark their prices by prices[parent] + cost of that node. If k becomes 0 then break the while loop because either cost is calculated or we consumed k+1 stops. Follow the steps below to solve the problem:

Increase the value of k by 1.
Initialize a vector of pair adj[n] and construct the adjacency list for the graph.
Initialize a vector prices[n] with values -1.
Initialize a queue of pair q[].
Push the pair {src, 0} into the queue and set the value of prices[0] as 0.
Traverse in a while loop until the queue becomes empty and perform the following steps:
- If k equals 0 then break.
- Initialize the variable sz as the size of the queue.
- Traverse in a while loop until sz is greater than 0 and perform the following tasks:
  - Initialize the variables node as the first value of the front pair of the queue and cost as the second value of the front pair of the queue.
  - Iterate over the range [0, adj[node].size()) using the variable it and perform the following tasks:
    - If prices[it.first] equals -1 or cost + it.second is less than prices[it.first] then set the value of prices[it.first] as cost + it.second and push the pair {it.first, cost + it.second} into the queue.
- Reduce the value of k by 1.
After performing the above steps, print the value of prices[dst] as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost
// from src to dst with at most k stops
int findCheapestCost(int n,
                     vector<vector<int> >& graph,
                     int src, int dst, int k)
{
      //if the destination cannot be reached
      if(dst > n)
      return -1;
    // Increase k by 1 Because on reaching
    // destination, k becomes k+1
    k = k + 1;
 
    // Making Adjacency List
    vector<pair<int, int> > adj[n];
 
    // U->{v, wt}
    for (auto it : graph) {
        adj[it[0]].push_back({ it[1], it[2] });
    }
 
    // Vector for Storing prices
    vector<int> prices(n, -1);
 
    // Queue for storing vertex and cost
    queue<pair<int, int> > q;
 
    q.push({ src, 0 });
    prices[src] = 0;
 
    while (!q.empty()) {
 
        // If all the k stops are used,
        // then break
        if (k == 0)
            break;
 
        int sz = q.size();
        while (sz--) {
            int node = q.front().first;
            int cost = q.front().second;
            q.pop();
 
            for (auto it : adj[node]) {
                if (prices[it.first] == -1
                    or cost + it.second
                           < prices[it.first]) {
                    prices[it.first] = cost + it.second;
                    q.push({ it.first, cost + it.second });
                }
            }
        }
        k--;
    }
    return prices[dst];
}
 
// Driver Code
int main()
{
    int n = 6;
    vector<vector<int> > graph
        = { { 0, 1, 10 }, { 1, 2, 20 }, { 2, 5, 30 }, { 1, 3, 10 }, { 3, 4, 10 }, { 4, 5, 10 } };
 
    int src = 0;
    int dst = 5;
    int k = 2;
    cout << findCheapestCost(n, graph, src, dst, k)
         << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
public class GFG{
  static class pair
  { 
    int first, second; 
    public pair(int first, int second)  
    { 
      this.first = first; 
      this.second = second; 
    }    
  } 
  // Function to find the minimum cost
  // from src to dst with at most k stops
  static int findCheapestCost(int n,
                              int[][] graph,
                              int src, int dst, int k)
  {
    //if the destination cannot be reached
      if(dst > n)
      return -1;
    // Increase k by 1 Because on reaching
    // destination, k becomes k+1
    k = k + 1;
 
    // Making Adjacency List
    Vector<pair> []adj = new Vector[n];
    for (int i = 0; i < adj.length; i++)
      adj[i] = new Vector<pair>();
 
    // U.{v, wt}
    for (int it[] : graph) {
      adj[it[0]].add(new pair( it[1], it[2] ));
    }
 
    // Vector for Storing prices
    int []prices = new int[n];
    Arrays.fill(prices, -1);
 
    // Queue for storing vertex and cost
    Queue<pair > q = new LinkedList<>();
 
    q.add(new pair( src, 0 ));
    prices[src] = 0;
 
    while (!q.isEmpty()) {
 
      // If all the k stops are used,
      // then break
      if (k == 0)
        break;
 
      int sz = q.size();
      while (sz-- >0) {
        int node = q.peek().first;
        int cost = q.peek().second;
        q.remove();
 
        for (pair it : adj[node]) {
          if (prices[it.first] == -1
              || cost + it.second
              < prices[it.first]) {
            prices[it.first] = cost + it.second;
            q.add(new pair( it.first, cost + it.second ));
          }
        }
      }
      k--;
    }
    return prices[dst];
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int n = 6;
    int[][] graph
      = { { 0, 1, 10 }, { 1, 2, 20 }, { 2, 5, 30 }, { 1, 3, 10 }, { 3, 4, 10 }, { 4, 5, 10 } };
 
    int src = 0;
    int dst = 5;
    int k = 2;
    System.out.print(findCheapestCost(n, graph, src, dst, k)
                     +"\n");
 
  }
}
 
// This code is contributed by 29AjayKumar

Python3

# python3 program for the above approach
from collections import deque
 
# Function to find the minimum cost
# from src to dst with at most k stops
 
 
def findCheapestCost(n, graph, src, dst, k):
 
    # if the destination cannot be reached
    if dst > n:
      return -1;
    # Increase k by 1 Because on reaching
    # destination, k becomes k+1
    k = k + 1
 
    # Making Adjacency List
    adj = [[] for _ in range(n)]
 
    # U->{v, wt}
    for it in graph:
        adj[it[0]].append([it[1], it[2]])
 
    # Vector for Storing prices
    prices = [-1 for _ in range(n)]
 
    # Queue for storing vertex and cost
    q = deque()
 
    q.append([src, 0])
    prices[src] = 0
 
    while (len(q) != 0):
 
        # If all the k stops are used,
        # then break
        if (k == 0):
            break
 
        sz = len(q)
        while (True):
            sz -= 1
 
            pr = q.popleft()
 
            node = pr[0]
            cost = pr[1]
 
            for it in adj[node]:
                if (prices[it[0]] == -1
                        or cost + it[1]
                        < prices[it[0]]):
                    prices[it[0]] = cost + it[1]
                    q.append([it[0], cost + it[1]])
 
            if sz == 0:
                break
        k -= 1
 
    return prices[dst]
 
# Driver Code
if __name__ == "__main__":
 
    n = 6
    graph = [
            [0, 1, 10],
            [1, 2, 20],
            [2, 5, 30],
            [1, 3, 10],
            [3, 4, 10],
            [4, 5, 10]]
 
    src = 0
    dst = 5
    k = 2
    print(findCheapestCost(n, graph, src, dst, k))
 
    # This code is contributed by rakeshsahni

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Function to find the minimum cost
    // from src to dst with at most k stops
    public static int findCheapestCost(int n, int[,] graph, int src, int dst, int k)
    {
        // if the destination cannot be reached
        if (dst > n)
        {
            return -1;
        }
 
        // Increase k by 1 Because on reaching
        // destination, k becomes k+1
        k = k + 1;
 
        // Making Adjacency List
        List<List<int[]>> adj = new List<List<int[]>>();
        for (int i = 0; i < n; i++)
        {
            adj.Add(new List<int[]>());
        }
 
        // U->{v, wt}
        for (int i = 0; i < graph.GetLength(0); i++)
        {
            adj[graph[i, 0]].Add(new int[] { graph[i, 1], graph[i, 2] });
        }
 
        // Vector for Storing prices
        int[] prices = new int[n];
        for (int i = 0; i < n; i++)
        {
            prices[i] = -1;
        }
 
        // Queue for storing vertex and cost
        Queue<int[]> q = new Queue<int[]>();
        q.Enqueue(new int[] { src, 0 });
        prices[src] = 0;
 
        while (q.Count != 0)
        {
            // If all the k stops are used,
            // then break
            if (k == 0)
            {
                break;
            }
 
            int sz = q.Count;
            while (sz-- > 0)
            {
                int[] pr = q.Dequeue();
 
                int node = pr[0];
                int cost = pr[1];
 
                foreach (int[] it in adj[node])
                {
                    if (prices[it[0]] == -1
                        || cost + it[1] < prices[it[0]])
                    {
                        prices[it[0]] = cost + it[1];
                        q.Enqueue(new int[] { it[0], cost + it[1] });
                    }
                }
            }
 
            k--;
        }
 
        return prices[dst];
    }
 
    public static void Main()
    {
        int n = 6;
        int[,] graph = {
            {0, 1, 10},
            {1, 2, 20},
            {2, 5, 30},
            {1, 3, 10},
            {3, 4, 10},
            {4, 5, 10}
        };
 
        int src = 0;
        int dst = 5;
        int k = 2;
        Console.WriteLine(findCheapestCost(n, graph, src, dst, k));
    }
}

Javascript

function findCheapestCost(n, graph, src, dst, k) {
  // if the destination cannot be reached
  if (dst > n) {
    return -1;
  }
 
  // Increase k by 1 Because on reaching
  // destination, k becomes k+1
  k = k + 1;
 
  // Making Adjacency List
  let adj = Array.from({ length: n }, () => []);
  for (let i = 0; i < graph.length; i++) {
    adj[graph[i][0]].push([graph[i][1], graph[i][2]]);
  }
 
  // Vector for Storing prices
  let prices = Array.from({ length: n }, () => -1);
 
  // Queue for storing vertex and cost
  let q = [];
  q.push([src, 0]);
  prices[src] = 0;
 
  while (q.length != 0) {
    // If all the k stops are used,
    // then break
    if (k == 0) {
      break;
    }
 
    let sz = q.length;
    while (sz > 0) {
      sz -= 1;
      let pr = q.shift();
      let node = pr[0];
      let cost = pr[1];
 
      for (let i = 0; i < adj[node].length; i++) {
        let it = adj[node][i];
        if (prices[it[0]] == -1 || cost + it[1] < prices[it[0]]) {
          prices[it[0]] = cost + it[1];
          q.push([it[0], cost + it[1]]);
        }
      }
 
      if (sz == 0) {
        break;
      }
    }
 
    k -= 1;
  }
 
  return prices[dst];
}
 
let n = 6;
let graph = [  [0, 1, 10],
  [1, 2, 20],
  [2, 5, 30],
  [1, 3, 10],
  [3, 4, 10],
  [4, 5, 10],
];
let src = 0;
let dst = 5;
let k = 2;
 
console.log(findCheapestCost(n, graph, src, dst, k));

Output

Time Complexity: O(n*k)
Auxiliary Space: O(n)

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!