Minimum cost path from source node to destination node via K intermediate nodes | C ++ program for the above approach ; Function to find the minimum cost path from the source vertex to destination vertex via K intermediate vertices ; Initialize the adjacency list ; Generate the adjacency list ; Initialize the minimum priority queue ; Stores the minimum cost to travel between vertices via K intermediate nodes ; Push the starting vertex , cost to reach and the number of remaining vertices ; Pop the top element of the stack ; If destination is reached ; Return the cost ; If all stops are exhausted ; Find the neighbour with minimum cost ; Pruning ; Update cost ; Update priority queue ; If no path exists ; Driver Code ; Function Call to find the path from src to dist via k nodes having least sum of weights
#include <bits/stdc++.h> NEW_LINE using namespace std ; int leastWeightedSumPath ( int n , vector < vector < int > > & edges , int src , int dst , int K ) { unordered_map < int , vector < pair < int , int > > > graph ; for ( vector < int > & edge : edges ) { graph [ edge [ 0 ] ] . push_back ( make_pair ( edge [ 1 ] , edge [ 2 ] ) ) ; } priority_queue < vector < int > , vector < vector < int > > , greater < vector < int > > > pq ; vector < vector < int > > costs ( n , vector < int > ( K + 2 , INT_MAX ) ) ; costs [ src ] [ K + 1 ] = 0 ; pq . push ( { 0 , src , K + 1 } ) ; while ( ! pq . empty ( ) ) { auto top = pq . top ( ) ; pq . pop ( ) ; if ( top [ 1 ] == dst ) return top [ 0 ] ; if ( top [ 2 ] == 0 ) continue ; for ( auto neighbor : graph [ top [ 1 ] ] ) { if ( costs [ neighbor . first ] [ top [ 2 ] - 1 ] < neighbor . second + top [ 0 ] ) { continue ; } costs [ neighbor . first ] [ top [ 2 ] - 1 ] = neighbor . second + top [ 0 ] ; pq . push ( { neighbor . second + top [ 0 ] , neighbor . first , top [ 2 ] - 1 } ) ; } } return -1 ; } int main ( ) { int n = 3 , src = 0 , dst = 2 , k = 1 ; vector < vector < int > > edges = { { 0 , 1 , 100 } , { 1 , 2 , 100 } , { 0 , 2 , 500 } } ; cout << leastWeightedSumPath ( n , edges , src , dst , k ) ; return 0 ; }