Single source shortest path between two cities

0 0 23 minutes read

Given a graph of N Nodes and E edges in form of {U, V, W} such that there exists an edge between U and V with weight W. You are given an integer K and source src and destination dst. The task is to find the cheapest cost path from given source to destination from K stops.
Examples:

Input: N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The Cheapest Price is from City 0 to City 2. With just one stop, it just costs 200 which is our Output.
Input: N = 3, edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0
Output: 500

Method 1: Using Depth First Search

Explore the current node and keep exploring its children.
Use a map to store the visited node in pair with stops and distance as value.
Break the recursion tree if the key is present in the map.
Find the answer (minimum cost) for each recursion tree and return it.

Below is the implementation of our approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure to implement hashing to
// stores pairs in map
struct pair_hash {
    template <class T1, class T2>
    std::size_t
    operator()(const std::pair<T1, T2>& pair) const
    {
        return std::hash<T1>()(pair.first)
               ^ std::hash<T2>()(pair.second);
    }
};
 
// DFS memoization
vector<vector<int> > adjMatrix;
typedef std::pair<int, int> pair1;
unordered_map<pair1, int, pair_hash> mp;
 
// Function to implement DFS Traversal
long DFSUtility(int node, int stops,
                int dst, int cities)
{
    // Base Case
    if (node == dst)
        return 0;
 
    if (stops < 0) {
        return INT_MAX;
    }
 
    pair<int, int> key(node, stops);
 
    // Find value with key in a map
    if (mp.find(key) != mp.end()) {
        return mp[key];
    }
 
    long ans = INT_MAX;
 
    // Traverse adjacency matrix of
    // source node
    for (int neighbour = 0;
         neighbour < cities;
         ++neighbour) {
 
        long weight
            = adjMatrix[node][neighbour];
 
        if (weight > 0) {
 
            // Recursive DFS call for
            // child node
            long minVal
                = DFSUtility(neighbour,
                             stops - 1,
                             dst, cities);
 
            if (minVal + weight > 0)
                ans = min(ans,
                          minVal
                              + weight);
        }
    }
 
    mp[key] = ans;
 
    // Return ans
    return ans;
}
 
// Function to find the cheapest price
// from given source to destination
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
 
    // Resize Adjacency Matrix
    adjMatrix.resize(cities + 1,
                     vector<int>(cities + 1, 0));
 
    // Traverse flight[][]
    for (auto item : flights) {
        // Create Adjacency Matrix
        adjMatrix[item[0]][item[1]] = item[2];
    }
 
    // DFS Call to find shortest path
    long ans = DFSUtility(src, stops,
                          dst, cities);
 
    // Return the cost
    return ans >= INT_MAX ? -1 : (int)ans;
    ;
}
 
// Driver Code
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops);
 
    cout << ans;
    return 0;
}

Java

// Java program for the above approach
import java.util.HashMap;
 
public class SingleS {
 
    // DFS memoization
    static int adjMatrix[][];
    static HashMap<int[], Integer> mp
        = new HashMap<int[], Integer>();
 
    // Function to implement DFS Traversal
    static int DFSUtility(int node, int stops, int dst,
                          int cities)
    {
        // Base Case
        if (node == dst)
            return 0;
 
        if (stops < 0)
            return Integer.MAX_VALUE;
 
        int[] key = new int[] { node, stops };
 
        // Find value with key in a map
        if (mp.containsKey(key))
            return mp.get(mp);
 
        int ans = Integer.MAX_VALUE;
 
        // Traverse adjacency matrix of
        // source node
        for (int neighbour = 0; neighbour < cities;
             ++neighbour) {
            int weight = adjMatrix[node][neighbour];
 
            if (weight > 0) {
                // Recursive DFS call for
                // child node
                int minVal = DFSUtility(
                    neighbour, stops - 1, dst, cities);
 
                if (minVal + weight > 0)
                    ans = Math.min(ans, minVal + weight);
            }
            mp.put(key, ans);
        }
        // Return ans
        return ans;
    }
 
    // Function to find the cheapest price
    // from given source to destination
    static int findCheapestPrice(int cities,
                                 int[][] flights, int src,
                                 int dst, int stops)
    {
        // Resize Adjacency Matrix
        adjMatrix = new int[cities + 1][cities + 1];
 
        // Traverse flight[][]
        for (int[] item : flights) {
            // Create Adjacency Matrix
            adjMatrix[item[0]][item[1]] = item[2];
        }
 
        // DFS Call to find shortest path
        int ans = DFSUtility(src, stops, dst, cities);
 
        // Return the cost
        return ans >= Integer.MAX_VALUE ? -1 : ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input flight : :Source,
        // Destination, Cost
        int[][] flights
            = { { 4, 1, 1 },  { 1, 2, 3 }, { 0, 3, 2 },
                { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
        // vec, n, stops, src, dst
        int stops = 2;
        int totalCities = 5;
        int sourceCity = 0;
        int destCity = 4;
 
        // Function Call
        int ans = findCheapestPrice(totalCities, flights,
                                    sourceCity, destCity,
                                    stops);
 
        System.out.println(ans);
    }
}
 
// This code is contributed by Lovely Jain

Python3

# Python3 program for the above approach
 
# DFS memoization
adjMatrix=[]
mp=dict()
 
# Function to implement DFS Traversal
def DFSUtility(node, stops, dst, cities):
    # Base Case
    if (node == dst):
        return 0
 
    if (stops < 0) :
        return 1e9
 
    key=(node, stops)
 
    # Find value with key in a map
    if key in mp:
        return mp[key]
 
    ans = 1e9
 
    # Traverse adjacency matrix of
    # source node
    for neighbour in range(cities):
        weight = adjMatrix[node][neighbour]
 
        if (weight > 0) :
 
            # Recursive DFS call for
            # child node
            minVal = DFSUtility(neighbour, stops - 1, dst, cities)
 
            if (minVal + weight > 0):
                ans = min(ans, minVal + weight)
         
     
 
    mp[key] = ans
 
    # Return ans
    return ans
 
 
# Function to find the cheapest price
# from given source to destination
def findCheapestPrice(cities, flights, src, dst, stops):
    global adjMatrix
    # Resize Adjacency Matrix
    adjMatrix=[[0]*(cities + 1) for _ in range(cities + 1)]
 
    # Traverse flight[][]
    for item in flights:
        # Create Adjacency Matrix
        adjMatrix[item[0]][item[1]] = item[2]
     
 
    # DFS Call to find shortest path
    ans = DFSUtility(src, stops, dst, cities)
 
    # Return the cost
    return -1 if ans >= 1e9 else int(ans)
     
 
 
# Driver Code
if __name__ == '__main__':
    # Input flight : :Source,
    # Destination, Cost
    flights = [[ 4, 1, 1 ],[ 1, 2, 3] , [ 0, 3, 2] , [ 0, 4, 10] , [ 3, 1, 1] , [ 1, 4, 3]]  
 
    # vec, n, stops, src, dst
    stops = 2
    totalCities = 5
    sourceCity = 0
    destCity = 4
 
    # Function Call
    ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops)
 
    print(ans)

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // DFS memoization
  static int[][] adjMatrix;
  static Dictionary<int[], int> mp = new Dictionary<int[], int>();
 
  // Function to implement DFS Traversal
  static int DFSUtility(int node, int stops, int dst, int cities)
  {
    // Base Case
    if (node == dst){
      return 0;
    }
 
    if (stops < 0){
      return Int32.MaxValue;
    }
 
    int[] key = new int[] { node, stops };
 
    // Find value with key in a map
    if (mp.ContainsKey(key)){
      return mp[key];
    }
 
    int ans = Int32.MaxValue;
 
    // Traverse adjacency matrix of
    // source node
    for (int neighbour = 0 ; neighbour < cities ; ++neighbour) {
      int weight = adjMatrix[node][neighbour];
 
      if (weight > 0) {
        // Recursive DFS call for
        // child node
        int minVal = DFSUtility(neighbour, stops - 1, dst, cities);
 
        if (minVal + weight > 0){
          ans = Math.Min(ans, minVal + weight);
        }
      }
      if(!mp.ContainsKey(key)){
        mp.Add(key, 0);
      }
      mp[key] = ans;
    }
    // Return ans
    return ans;
  }
 
  // Function to find the cheapest price
  // from given source to destination
  static int findCheapestPrice(int cities, int[][] flights, int src, int dst, int stops)
  {
    // Resize Adjacency Matrix
    adjMatrix = new int[cities + 1][];
    for(int i = 0 ; i <= cities ; i++){
      adjMatrix[i] = new int[cities + 1];
    }
 
    // Traverse flight[][]
    foreach (int[] item in flights) {
      // Create Adjacency Matrix
      adjMatrix[item[0]][item[1]] = item[2];
    }
 
    // DFS Call to find shortest path
    int ans = DFSUtility(src, stops, dst, cities);
 
    // Return the cost
    return ans >= Int32.MaxValue ? -1 : ans;
  }
 
  // Driver code
  public static void Main(string[] args){
 
    // Input flight : :Source,
    // Destination, Cost
    int[][] flights = new int[][]{
      new int[]{ 4, 1, 1 },
      new int[]{ 1, 2, 3 },
      new int[]{ 0, 3, 2 },
      new int[]{ 0, 4, 10 },
      new int[]{ 3, 1, 1 },
      new int[]{ 1, 4, 3 }
    };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    int ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
 
    Console.WriteLine(ans);
 
  }
}
 
// This code is contributed by entertain2022.

Javascript

const pair_hash = {
    // Function to implement hashing
    operator(pair) {
        return (
            Math.hash(pair.first) ^ Math.hash(pair.second)
        );
    }
};
 
// DFS memoization
let adjMatrix = [];
let mp = new Map();
 
// Function to implement DFS Traversal
function DFSUtility(node, stops, dst, cities)
{
 
    // Base Case
    if (node === dst) return 0;
    if (stops < 0) return Number.MAX_SAFE_INTEGER;
    let key = new Map();
     
    // Find value with key in a map
    if (mp.has(key)) return mp.get(key);
    let ans = Number.MAX_SAFE_INTEGER;
     
    // Traverse adjacency matrix of
    // source node
    for (let neighbour = 0; neighbour < cities; neighbour++) {
        let weight = adjMatrix[node][neighbour];
        if (weight > 0)
        {
         
            // Recursive DFS call for
            // child node
            let minVal = DFSUtility(neighbour, stops - 1, dst, cities);
            if (minVal + weight > 0)
                ans = Math.min(ans, minVal + weight);
        }
    }
    mp.set(key, ans);
     
    // Return ans
    return ans;
}
 
// Function to find the cheapest price
// from given source to destination
function findCheapestPrice(cities, flights, 
src, dst, stops)
{
 
    // Resize Adjacency Matrix
    adjMatrix.resize = cities + 1;
    for (let i = 0; i < cities + 1; i++) {
        adjMatrix[i] = Array(cities + 1).fill(0);
    }
     
    // Traverse flight[][]
    for (let item of flights)
    {
     
        // Create Adjacency Matrix
        adjMatrix[item[0]][item[1]] = item[2];
    }
     
    // DFS Call to find shortest path
    let ans = DFSUtility(src, stops, dst, cities);
     
    // Return the cost
    return ans >= Number.MAX_SAFE_INTEGER ? -1 : ans;
}
 
// Driver Code
// Input flight : {Source,
// Destination, Cost}
let flights = [
    [4, 1, 1],
    [1, 2, 3],
    [0, 3, 2],
    [0, 4, 10],
    [3, 1, 1],
    [1, 4, 3],
];
 
// vec, n, stops, src, dst
let stops = 2;
let totalCities = 5;
let sourceCity = 0;
let destCity = 4;
 
// Function Call
let ans = findCheapestPrice(
    totalCities,
    flights,
    sourceCity,
    destCity,
    stops
);
console.log(ans);
 
// This code is contributed by ishankhandelwals.

Output:

Time Complexity: O(V + E), where V is the number of nodes and E is the edges.
Auxiliary Space: O(V)

Method 2: Using Breadth-First Search

The idea is to use Queue to perform BFS Traversal.
Perform traversal from current node and insert root node in the queue.
Traverse the queue and explore the current node and its siblings. Then insert the siblings of the node in the queue.
While exploring each sibling and keep pushing the entries in the queue if the cost is less and update the minimum cost.
Print the minimum cost after the above traversal.

Below is the implementation of our approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <unordered_map>
 
using namespace std;
// BSF Memoization
typedef tuple<int, int, int> tupl;
 
// Function to implement BFS
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
    unordered_map<int,
                  vector<pair<int, int> > >
        adjList;
 
    // Traverse flight[][]
    for (auto flight : flights) {
 
        // Create Adjacency Matrix
        adjList[flight[0]].push_back(
            { flight[1], flight[2] });
    }
 
    // < city, distancefromsource > pair
    queue<pair<int, int> >
        q;
    q.push({ src, 0 });
 
    // Store the Result
    int srcDist = INT_MAX;
 
    // Traversing the Matrix
    while (!q.empty() && stops-- >= 0) {
 
        int qSize = q.size();
 
        for (int i = 0; i < qSize; i++) {
            pair<int, int> curr = q.front();
            q.pop();
 
            for (auto next : adjList[curr.first]) {
 
                // If source distance is already
                // least the skip this iteration
                if (srcDist < curr.second
                                  + next.second)
                    continue;
 
                q.push({ next.first,
                         curr.second
                             + next.second });
 
                if (dst == next.first) {
                    srcDist = min(
                        srcDist, curr.second
                                     + next.second);
                }
            }
        }
    }
 
    // Returning the Answer
    return srcDist == INT_MAX ? -1 : srcDist;
}
 
// Driver Code
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops);
    cout << ans;
    return 0;
}

Java

// Jaca program of the above approach
import java.util.*;
 
public class Main
{
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Input flight : {Source,
    // Destination, Cost}
    int[][] flights
      = { { 4, 1, 1 },  { 1, 2, 3 }, { 0, 3, 2 },
         { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(totalCities, flights,
                                 sourceCity, destCity,
                                 stops);
    System.out.println(ans);
  }
  public static long findCheapestPrice(int cities,
                                       int[][] flights,
                                       int src, int dst,
                                       int stops)
  {
    Map<Integer, List<int[]> > adjList
      = new HashMap<>();
 
    // Traverse flight[][]
    for (int[] flight : flights) {
      // Create Adjacency Matrix
      adjList
        .computeIfAbsent(flight[0],
                         k -> new ArrayList<>())
        .add(new int[] { flight[1], flight[2] });
    }
 
    // < city, distancefromsource > []
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[] { src, 0 });
 
    // Store the Result
    long srcDist = Integer.MAX_VALUE;
 
    // Traversing the Matrix
    while (!q.isEmpty() && stops-- >= 0) {
      int qSize = q.size();
 
      for (int i = 0; i < qSize; i++) {
        int[] curr = q.poll();
 
        for (int[] next : adjList.getOrDefault(
          curr[0], new ArrayList<>())) {
          // If source distance is already
          // least the skip this iteration
          if (srcDist < curr[1] + next[1])
            continue;
 
          q.offer(new int[] {
            next[0], curr[1] + next[1] });
 
          if (dst == next[0])
            srcDist = Math.min(
            srcDist, curr[1] + next[1]);
        }
      }
    }
 
    // Returning the Answer
    return srcDist == Integer.MAX_VALUE ? -1 : srcDist;
  }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Python3

# Python3 program of the above approach
 
from queue import Queue as Q
# Function to implement BFS
def findCheapestPrice(cities, flights, src, dst, stops):
    adjList=dict()
 
    # Traverse flight[][]
    for flight in flights :
 
        # Create Adjacency Matrix
        if flight[0] in adjList:
            adjList[flight[0]].append(
                (flight[1], flight[2]))
        else:
            adjList[flight[0]]=[(flight[1], flight[2])]
     
    q=Q()
    q.put((src, 0))
 
    # Store the Result
    srcDist = 1e9
    # Traversing the Matrix
    while (not q.empty() and stops >= 0) :
        stops-=1
 
        for i in range(q.qsize()) :
            curr = q.get()
 
            for nxt in adjList[curr[0]]:
 
                # If source distance is already
                # least the skip this iteration
                if (srcDist < curr[1] + nxt[1]):
                    continue
 
                q.put((nxt[0],curr[1] + nxt[1]))
 
                if (dst == nxt[0]):
                    srcDist = min( srcDist, curr[1] + nxt[1])
                 
    # Returning the Answer
    return -1 if srcDist == 1e9 else srcDist
 
 
# Driver Code
if __name__ == '__main__':
    # Input flight : :Source,
    # Destination, Cost
    flights= [[ 4, 1, 1 ],[ 1, 2, 3] , [ 0, 3, 2] , [ 0, 4, 10] , [ 3, 1, 1] , [ 1, 4, 3]]  
 
    # vec, n, stops, src, dst
    stops = 2
    totalCities = 5
 
    # Given source and destination
    sourceCity = 0
    destCity = 4
 
    # Function Call
    ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity,
        stops)
    print(ans)

C#

// C# program of the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
public class GFG {
  public static int findCheapestPrice(int n,
                                      int[, ] flights,
                                      int src, int dst,
                                      int K)
  {
    var adjList
      = new Dictionary<int,
    List<Tuple<int, int> > >();
 
    // Traverse flight[][]
    for (int i = 0; i < flights.GetLength(0); i++) {
      // Create Adjacency Matrix
      if (!adjList.ContainsKey(flights[i, 0])) {
        adjList.Add(flights[i, 0],
                    new List<Tuple<int, int> >());
      }
      adjList[flights[i, 0]].Add(
        Tuple.Create(flights[i, 1], flights[i, 2]));
    }
 
    // < city, distancefromsource > []
    var q = new Queue<(int, int)>();
    q.Enqueue((src, 0));
 
    // Store the Result
    var srcDist = Int32.MaxValue;
 
    // Traversing the Matrix
    while (q.Count > 0 && K-- >= 0) {
      var qSize = q.Count;
 
      for (var i = 0; i < qSize; i++) {
        var curr = q.Dequeue();
 
        foreach(var next in adjList[curr.Item1])
        {
          // If source distance is already
          // least the skip this iteration
          if (srcDist < curr.Item2 + next.Item2)
            continue;
 
          q.Enqueue((next.Item1,
                     curr.Item2 + next.Item2));
          if (dst == next.Item1) {
            srcDist = Math.Min(
              srcDist,
              curr.Item2 + next.Item2);
          }
        }
      }
    }
    // Returning the Answer
    return srcDist == Int32.MaxValue ? -1 : srcDist;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    // Input flight : {Source,
    // Destination, Cost}
    int[, ] flights
      = new int[, ] { { 4, 1, 1 }, { 1, 2, 3 },
                     { 0, 3, 2 }, { 0, 4, 10 },
                     { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(totalCities, flights,
                                 sourceCity, destCity,
                                 stops);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Javascript

function findCheapestPrice(cities, flights, src, dst, stops) {
  const adjList = new Map();
 
  // Traverse flight[][]
  for (let i = 0; i < flights.length; i++) {
    const flight = flights[i];
     
    // Create Adjacency Matrix
    const dest = flight[1];
    const cost = flight[2];
    const neighbors = adjList.get(flight[0]) || [];
    neighbors.push([dest, cost]);
    adjList.set(flight[0], neighbors);
  }
 
  // < city, distancefromsource > []
  const q = [];
  q.push([src, 0]);
 
  // Store the Result
  let srcDist = Infinity;
 
  // Traversing the Matrix
  while (q.length > 0 && stops-- >= 0) {
    const qSize = q.length;
 
    for (let i = 0; i < qSize; i++) {
      const curr = q.shift();
 
      const neighbors = adjList.get(curr[0]) || [];
      for (let j = 0; j < neighbors.length; j++) {
        const next = neighbors[j];
         
        // If source distance is already
        // least the skip this iteration
        if (srcDist < curr[1] + next[1]) {
          continue;
        }
 
        q.push([next[0], curr[1] + next[1]]);
        if (dst === next[0]) {
          srcDist = Math.min(srcDist, curr[1] + next[1]);
        }
      }
    }
  }
 
  // Returning the Answer
  return srcDist === Infinity ? -1 : srcDist;
}
 
// Driver Code
const flights = [
  [4, 1, 1],
  [1, 2, 3],
  [0, 3, 2],
  [0, 4, 10],
  [3, 1, 1],
  [1, 4, 3]
];
const stops = 2;
const totalCities = 5;
const sourceCity = 0;
const destCity = 4;
 
const ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
console.log(ans);

Output:

Time Complexity: O(Stops* N * N) where N is the Product of Cities and Size in Queue
Auxiliary Space: O(N)

Method 3: Using Dijkstra Algorithm

Update the distance of all the vertices from the source.
The vertices that are not directly connected from the source are marked with infinity and vertices that are directly connected are updated with the correct distance.
Start from the source, and extract next min vertices. This will ensure the minimum cost.
Do Edge Relaxation at each step: D denotes Distance and w denotes weights
1. If D[u] + w(u, z) < D[z] then
2. D[z] = D[u] + w(u, z)

Here is the implementation of our approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
#include <tuple>
using namespace std;
 
typedef tuple<int, int, int> tupl;
long findCheapestPrice(int cities,
                       vector<vector<int> >& flights,
                       int src, int dst, int stops)
{
    // Adjacency Matrix
    vector<vector<pair<int, int> > > adjList(cities);
 
    // Traverse flight[][]
    for (auto flight : flights) {
        // Create Adjacency Matrix
        adjList[flight[0]].push_back(
            { flight[1], flight[2] });
    }
 
    // Implementing Priority Queue
    priority_queue<tupl, vector<tupl>,
                   greater<tupl> >
        pq;
 
    tupl t = make_tuple(0, src, stops);
    pq.push(t);
 
    // While PQ is not empty
    while (!pq.empty()) {
        tupl t = pq.top();
        pq.pop();
 
        if (src == dst)
            return 0;
 
        int cost = get<0>(t);
        int current = get<1>(t);
        int stop = get<2>(t);
 
        if (current == dst)
 
            // Return the Answer
            return cost;
 
        if (stop >= 0) {
            for (auto next : adjList[current]) {
 
                tupl t = make_tuple((cost
                                     + next.second),
                                    next.first,
                                    stop - 1);
                pq.push(t);
            }
        }
    }
    return -1;
}
 
int main()
{
    // Input flight : {Source,
    // Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity, stops);
    cout << ans;
    return 0;
}

Java

// Java code
import java.util.*;
import java.util.stream.Collectors;
 
public class Main {
    // Create a tuple class
    static class tupl implements Comparable<tupl> {
        int cost;
        int current;
        int stop;
 
        public tupl(int cost, int current, int stop)
        {
            this.cost = cost;
            this.current = current;
            this.stop = stop;
        }
 
        @Override public int compareTo(tupl o)
        {
            return this.cost - o.cost;
        }
    };
 
    // Function to find the cheapest
    // price from source to destination
    // using at-most k stops
    static long
    findCheapestPrice(int cities,
                      List<List<Integer> > flights, int src,
                      int dst, int stops)
    {
 
        // Adjacency Matrix
        List<List<int[]> > adjList = new ArrayList<>();
        for (int i = 0; i < cities; i++)
            adjList.add(new ArrayList<>());
 
        // Traverse flight[][]
        for (List<Integer> flight : flights) {
            // Create Adjacency Matrix
            adjList.get(flight.get(0))
                .add(new int[] { flight.get(1),
                                 flight.get(2) });
        }
 
        // Implementing Priority Queue
        PriorityQueue<tupl> pq = new PriorityQueue<>();
        tupl t = new tupl(0, src, stops);
        pq.add(t);
 
        // While PQ is not empty
        while (!pq.isEmpty()) {
            tupl t1 = pq.poll();
            int cost = t1.cost;
            int current = t1.current;
            int stop = t1.stop;
 
            if (current == dst)
 
                // Return the Answer
                return cost;
 
            if (stop >= 0) {
                for (int[] next : adjList.get(current)) {
 
                    tupl t2 = new tupl((cost + next[1]),
                                       next[0], stop - 1);
                    pq.add(t2);
                }
            }
        }
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input flight : {Source,
        // Destination, Cost}
        List<List<Integer> > flights = Arrays.asList(
            Arrays.asList(4, 1, 1), Arrays.asList(1, 2, 3),
            Arrays.asList(0, 3, 2), Arrays.asList(0, 4, 10),
            Arrays.asList(3, 1, 1), Arrays.asList(1, 4, 3));
 
        // vec, n, stops, src, dst
        int stops = 2;
        int totalCities = 5;
 
        // Given source and destination
        int sourceCity = 0;
        int destCity = 4;
 
        // Function Call
        long ans = findCheapestPrice(totalCities, flights,
                                     sourceCity, destCity,
                                     stops);
 
        System.out.println(ans);
    }
}

Python3

# Python3 program for the above approach
import heapq as hq
 
 
def findCheapestPrice(cities, flights, src, dst, stops):
    # Adjacency Matrix
    adjList = [[] for _ in range(cities)]
    # Traverse flight[][]
    for flight in flights:
        # Create Adjacency Matrix
        adjList[flight[0]].append((flight[1], flight[2]))
 
    # Implementing Priority Queue
    pq = []
 
    t = (0, src, stops)
    hq.heappush(pq, t)
 
    # While PQ is not empty
    while (pq):
        t = hq.heappop(pq)
 
        if (src == dst):
            return 0
 
        cost, current, stop = t
 
        if (current == dst):
 
            # Return the Answer
            return cost
 
        if (stop >= 0):
            for nxt in adjList[current]:
 
                t = ((cost + nxt[1]), nxt[0], stop - 1)
                hq.heappush(pq, t)
    return -1
 
 
if __name__ == '__main__':
    # Input flight : :Source,
    # Destination, Cost
    flights = [[4, 1, 1], [1, 2, 3], [0, 3, 2],
               [0, 4, 10], [3, 1, 1], [1, 4, 3]]
 
    # vec, n, stops, src, dst
    stops = 2
    totalCities = 5
 
    # Given source and destination
    sourceCity = 0
    destCity = 4
 
    # Function Call
    ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity, stops)
    print(ans)

Javascript

function findCheapestPrice(cities, flights, src, dst, stops) {
  // Adjacency List
  const adjList = Array.from({ length: cities }, () => []);
 
  // Traverse flights[][]
  for (const flight of flights) {
    // Create Adjacency List
    adjList[flight[0]].push([flight[1], flight[2]]);
  }
 
  // Implementing Priority Queue
  const pq = [];
 
  const t = [0, src, stops];
  pq.push(t);
 
  // While PQ is not empty
  while (pq.length > 0) {
    const t = pq.shift();
 
    if (src == dst) {
      return 0;
    }
 
    const [cost, current, stop] = t;
 
    if (current == dst) {
      // Return the answer
      return cost;
    }
 
    if (stop >= 0) {
      for (const [nxt, price] of adjList[current]) {
        const t = [cost + price, nxt, stop - 1];
        pq.push(t);
      }
      pq.sort((a, b) => a[0] - b[0]);
    }
  }
 
  return -1;
}
 
// Input flight: [Source, Destination, Cost]
const flights = [  [4, 1, 1],
  [1, 2, 3],
  [0, 3, 2],
  [0, 4, 10],
  [3, 1, 1],
  [1, 4, 3],
];
 
// vec, n, stops, src, dst
const stops = 2;
const totalCities = 5;
 
// Given source and destination
const sourceCity = 0;
const destCity = 4;
 
// Function call
const ans = findCheapestPrice(
  totalCities,
  flights,
  sourceCity,
  destCity,
  stops
);
console.log(ans);

C#

//C# program for the above approach
using System;
using System.Collections.Generic;
 
public class MainClass
{
   
    public static int findCheapestPrice(int cities, int[][] flights, int src, int dst, int stops)
    {
        // Adjacency Matrix
        List<List<Tuple<int, int>>> adjList = new List<List<Tuple<int, int>>>();
        for (int i = 0; i < cities; i++)
        {
            adjList.Add(new List<Tuple<int, int>>());
        }
 
        // Traverse flight[][]
        foreach (int[] flight in flights)
        {
            // Create Adjacency Matrix
            adjList[flight[0]].Add(Tuple.Create(flight[1], flight[2]));
        }
 
        // Implementing Priority Queue
        List<Tuple<int, int, int>> pq = new List<Tuple<int, int, int>>();
 
        Tuple<int, int, int> t = Tuple.Create(0, src, stops);
        pq.Add(t);
 
        // While PQ is not empty
        while (pq.Count > 0)
        {
            t = pq[0];
            pq.RemoveAt(0);
 
            if (src == dst)
            {
                return 0;
            }
 
            int cost = t.Item1;
            int current = t.Item2;
            int stop = t.Item3;
 
            if (current == dst)
            {
                // Return the Answer
                return cost;
            }
 
            if (stop >= 0)
            {
                foreach (Tuple<int, int> nxt in adjList[current])
                {
                    t = Tuple.Create(cost + nxt.Item2, nxt.Item1, stop - 1);
                    pq.Add(t);
                }
                pq.Sort();
            }
        }
        return -1;
    }
 
    public static void Main()
    {
        // Input flight : :Source,
        // Destination, Cost
        int[][] flights = new int[][]{
            new int[]{4, 1, 1},
            new int[]{1, 2, 3},
            new int[]{0, 3, 2},
            new int[]{0, 4, 10},
            new int[]{3, 1, 1},
            new int[]{1, 4, 3}
        };
 
        // vec, n, stops, src, dst
        int stops = 2;
        int totalCities = 5;
 
        // Given source and destination
        int sourceCity = 0;
        int destCity = 4;
 
        // Function Call
        int ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
        Console.WriteLine(ans);
    }
}
 
//This code is contributed by shivamsharma215

Output:

Time Complexity: O(E+V log V) where V is the number of nodes and E is the edges.
Auxiliary Space: O(V)

Method 4: Using Bellmon Ford

Initialize distances from the source to all vertices as infinite and distance to the source itself as 0.
Do Edge Relaxation at each step: D denotes Distance and w denotes weights
- If D[u] + w(u, z) < D[z] then D[z] = D[u] + w(u, z)
The algorithm has been modified to solve the given problem instead of relaxing the graph V-1 times, we will do it for the given number of stops.

Below is the implementation of the above approach

C++

// C++ program of the above Approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
 
// Function to find the cheapest cost
// from source to destination using K stops
int findCheapestPrice(int cities,
                      vector<vector<int> >& flights,
                      int src, int dst, int stops)
{
    // Distance from source to all other nodes
    vector<int> dist(cities, INT_MAX);
    dist[src] = 0;
 
    // Do relaxation for V-1 vertices
    // here we need for K stops so we
    // will do relaxation for k+1 stops
    for (int i = 0; i <= stops; i++) {
 
        vector<int> intermediate(dist);
 
        for (auto flight : flights) {
 
            if (dist[flight[0]] != INT_MAX) {
                intermediate[flight[1]]
                    = min(intermediate[flight[1]],
                          dist[flight[0]]
                              + flight[2]);
            }
        }
 
        // Update the distance vector
        dist = intermediate;
    }
 
    // Return the final cost
    return dist[dst] == INT_MAX ? -1 : dist[dst];
}
 
// Driver Code
int main()
{
    // Input flight : {Source, Destination, Cost}
    vector<vector<int> > flights
        = { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    long ans = findCheapestPrice(
        totalCities, flights, sourceCity,
        destCity, stops);
    cout << ans;
    return 0;
}

Java

// Java program of the above approach
import java.util.*;
 
public class Main {
 
  // Function to find the cheapest cost
  // from source to destination using K stops
  public static int findCheapestPrice(
    int cities, ArrayList<ArrayList<Integer> > flights,
    int src, int dst, int stops)
  {
 
    // Distance from source to all other nodes
    ArrayList<Integer> dist = new ArrayList<Integer>();
    for (int i = 0; i < cities; i++) {
      dist.add(Integer.MAX_VALUE);
    }
    dist.set(src, 0);
     
    // Do relaxation for V-1 vertices
    // here we need for K stops so we
    // will do relaxation for k+1 stops
    for (int i = 0; i <= stops; i++) {
 
      ArrayList<Integer> intermediate
        = new ArrayList<Integer>(dist);
 
      for (ArrayList<Integer> flight : flights) {
 
        if (dist.get(flight.get(0))
            != Integer.MAX_VALUE) {
          intermediate.set(
            flight.get(1),
            Math.min(
              intermediate.get(flight.get(1)),
              dist.get(flight.get(0))
              + flight.get(2)));
        }
      }
 
      // Update the distance vector
      dist = intermediate;
    }
 
    // Return the final cost
    return dist.get(dst) == Integer.MAX_VALUE
      ? -1
      : dist.get(dst);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Input flight : {Source, Destination, Cost}
    ArrayList<ArrayList<Integer> > flights
      = new ArrayList<ArrayList<Integer> >();
    flights.add(
      new ArrayList<Integer>(Arrays.asList(4, 1, 1)));
    flights.add(
      new ArrayList<Integer>(Arrays.asList(1, 2, 3)));
    flights.add(
      new ArrayList<Integer>(Arrays.asList(0, 3, 2)));
    flights.add(new ArrayList<Integer>(
      Arrays.asList(0, 4, 10)));
    flights.add(
      new ArrayList<Integer>(Arrays.asList(3, 1, 1)));
    flights.add(
      new ArrayList<Integer>(Arrays.asList(1, 4, 3)));
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    int ans = findCheapestPrice(totalCities, flights,
                                sourceCity, destCity,
                                stops);
    System.out.println(ans);
  }
}
 
// This code is contributed by rishabmalhdijo

Python3

# Python3 program of the above Approach
 
# Function to find the cheapest cost
# from source to destination using K stops
def findCheapestPrice(cities, flights, src, dst, stops):
    # Distance from source to all other nodes
    dist=[1e9]*cities
    dist[src] = 0
 
    # Do relaxation for V-1 vertices
    # here we need for K stops so we
    # will do relaxation for k+1 stops
    for i in range(stops):
 
        intermediate=dist
 
        for flight in flights:
 
            if (dist[flight[0]] != 1e9) :
                intermediate[flight[1]] = min(intermediate[flight[1]], dist[flight[0]] + flight[2])
             
         
 
        # Update the distance vector
        dist = intermediate
     
 
    # Return the final cost
    return -1 if dist[dst] == 1e9 else dist[dst]
 
 
# Driver Code
if __name__ == '__main__':
    # Input flight : :Source, Destination, Cost
    flights = [[4, 1, 1], [1, 2, 3], [0, 3, 2],
               [0, 4, 10], [3, 1, 1], [1, 4, 3]]
 
    # vec, n, stops, src, dst
    stops = 2
    totalCities = 5
 
    # Given source and destination
    sourceCity = 0
    destCity = 4
 
    # Function Call
    ans = findCheapestPrice(
        totalCities, flights,
        sourceCity, destCity, stops)
    print(ans)

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class MainClass 
{
 
  // Function to find the cheapest cost
  // from source to destination using K stops
  public static int FindCheapestPrice(
    int cities, List<List<int>> flights,
    int src, int dst, int stops)
  {
 
    // Distance from source to all other nodes
    List<int> dist = new List<int>(Enumerable.Repeat(Int32.MaxValue, cities));
    dist[src] = 0;
 
    // Do relaxation for V-1 vertices
    // here we need for K stops so we
    // will do relaxation for k+1 stops
    for (int i = 0; i <= stops; i++) {
 
      List<int> intermediate = new List<int>(dist);
 
      foreach (List<int> flight in flights) {
 
        if (dist[flight[0]] != Int32.MaxValue) {
          intermediate[flight[1]] = Math.Min(
            intermediate[flight[1]],
            dist[flight[0]] + flight[2]);
        }
      }
 
      // Update the distance vector
      dist = intermediate;
    }
 
    // Return the final cost
    return dist[dst] == Int32.MaxValue ? -1 : dist[dst];
  }
 
  // Driver Code
  public static void Main() {
    // Input flight : {Source, Destination, Cost}
    List<List<int>> flights = new List<List<int>> {
      new List<int> {4, 1, 1},
      new List<int> {1, 2, 3},
      new List<int> {0, 3, 2},
      new List<int> {0, 4, 10},
      new List<int> {3, 1, 1},
      new List<int> {1, 4, 3}
    };
 
    // vec, n, stops, src, dst
    int stops = 2;
    int totalCities = 5;
 
    // Given source and destination
    int sourceCity = 0;
    int destCity = 4;
 
    // Function Call
    int ans = FindCheapestPrice(totalCities, flights,
                                sourceCity, destCity,
                                stops);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by Prajwal Kandekar

Javascript

// JavaScript program of the above Approach
 
// Function to find the cheapest cost
// from source to destination using K stops
function findCheapestPrice(cities,flights,src,dst,stops)
{
    // Distance from source to all other nodes
    var dist = Array(cities).fill(Number.MAX_VALUE);
    dist[src] = 0;
 
    // Do relaxation for V-1 vertices
    // here we need for K stops so we
    // will do relaxation for k+1 stops
    for (let i = 0; i <= stops; i++) {
 
        var intermediate = [...dist];
 
        for (let flight of flights) {
 
            if (dist[flight[0]] != Number.MAX_VALUE) {
                intermediate[flight[1]]
                    = Math.min(intermediate[flight[1]],
                               dist[flight[0]] + flight[2]);
            }
        }
 
        // Update the distance vector
        dist = [...intermediate];
    }
 
    // Return the final cost
    return dist[dst] == Number.MAX_VALUE ? -1 : dist[dst];
}
 
 
// Driver code
const flights = [
    [4, 1, 1], 
    [1, 2, 3], 
    [0, 3, 2], 
    [0, 4, 10], 
    [3, 1, 1], 
    [1, 4, 3]
];
 
let stops = 2;
let totalCities = 5;
 
let sourceCity = 0;
let destCity = 4;
 
let ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
 
console.log(ans);
 
// This code is contributed by ishankhandelwals.

Output:

Time Complexity: O(E*V) where V is the number of nodes and E is the edges.
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!