Minimum cost path from source node to destination node via K intermediate nodes | 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
def leastWeightedSumPath ( n , edges , src , dst , K ) : NEW_LINE INDENT graph = [ [ ] for i in range ( 3 ) ] NEW_LINE for edge in edges : NEW_LINE INDENT graph [ edge [ 0 ] ] . append ( [ edge [ 1 ] , edge [ 2 ] ] ) NEW_LINE DEDENT pq = [ ] NEW_LINE costs = [ [ 10 ** 9 for i in range ( K + 2 ) ] for i in range ( n ) ] NEW_LINE costs [ src ] [ K + 1 ] = 0 NEW_LINE pq . append ( [ 0 , src , K + 1 ] ) NEW_LINE pq = sorted ( pq ) [ : : - 1 ] NEW_LINE while ( len ( pq ) > 0 ) : NEW_LINE INDENT top = pq [ - 1 ] NEW_LINE del pq [ - 1 ] NEW_LINE if ( top [ 1 ] == dst ) : NEW_LINE INDENT return top [ 0 ] NEW_LINE DEDENT if ( top [ 2 ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for neighbor in graph [ top [ 1 ] ] : NEW_LINE INDENT if ( costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] < neighbor [ 1 ] + top [ 0 ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] = neighbor [ 1 ] + top [ 0 ] NEW_LINE pq . append ( [ neighbor [ 1 ] + top [ 0 ] , neighbor [ 0 ] , top [ 2 ] - 1 ] ) NEW_LINE DEDENT pq = sorted ( pq ) [ : : - 1 ] NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n , src , dst , k = 3 , 0 , 2 , 1 NEW_LINE edges = [ [ 0 , 1 , 100 ] , [ 1 , 2 , 100 ] , [ 0 , 2 , 500 ] ] NEW_LINE print ( leastWeightedSumPath ( n , edges , src , dst , k ) ) NEW_LINE DEDENT