Shortest path with exactly k edges in a directed and weighted graph | Set 2 | Java implementation of the above approach ; Function to find the smallest path with exactly K edges ; Array to store dp ; Initialising the array ; Loop to solve DP ; Initialising next state ; Recurrence relation ; Returning final answer ; Driver code ; Input edges ; Source and Destination ; Number of edges in path ; Calling the function
import java . util . ArrayList ; import java . util . Arrays ; class GFG { static class Pair < K , V > { K first ; V second ; public Pair ( K first , V second ) { this . first = first ; this . second = second ; } } static int inf = 100000000 ; static int smPath ( int s , int d , ArrayList < Pair < Pair < Integer , Integer > , Integer > > ed , int n , int k ) { int [ ] dis = new int [ n + 1 ] ; Arrays . fill ( dis , inf ) ; dis [ s ] = 0 ; for ( int i = 0 ; i < k ; i ++ ) { int [ ] dis1 = new int [ n + 1 ] ; Arrays . fill ( dis1 , inf ) ; for ( Pair < Pair < Integer , Integer > , Integer > it : ed ) dis1 [ it . first . second ] = Math . min ( dis1 [ it . first . second ] , dis [ it . first . first ] + it . second ) ; for ( int j = 0 ; j <= n ; j ++ ) dis [ j ] = dis1 [ j ] ; } if ( dis [ d ] == inf ) return - 1 ; else return dis [ d ] ; } public static void main ( String [ ] args ) { int n = 4 ; ArrayList < Pair < Pair < Integer , Integer > , Integer > > ed = new ArrayList < > ( Arrays . asList ( new Pair < Pair < Integer , Integer > , Integer > ( new Pair < Integer , Integer > ( 0 , 1 ) , 10 ) , new Pair < Pair < Integer , Integer > , Integer > ( new Pair < Integer , Integer > ( 0 , 2 ) , 3 ) , new Pair < Pair < Integer , Integer > , Integer > ( new Pair < Integer , Integer > ( 0 , 3 ) , 2 ) , new Pair < Pair < Integer , Integer > , Integer > ( new Pair < Integer , Integer > ( 1 , 3 ) , 7 ) , new Pair < Pair < Integer , Integer > , Integer > ( new Pair < Integer , Integer > ( 2 , 3 ) , 7 ) ) ) ; int s = 0 , d = 3 ; int k = 2 ; System . out . println ( smPath ( s , d , ed , n , k ) ) ; } }