Shortest path with exactly k edges in a directed and weighted graph | Dynamic Programming based Java program to find shortest path with exactly k edges ; Define number of vertices in the graph and inifinite value ; A naive recursive function to count walks from u to v with k edges ; Base cases ; Initialize result ; Go to all adjacents of u and recur ; driver program to test above function ; Let us create the graph shown in above diagram
import java . util . * ; import java . lang . * ; import java . io . * ; class ShortestPath { static final int V = 4 ; static final int INF = Integer . MAX_VALUE ; int shortestPath ( int graph [ ] [ ] , int u , int v , int k ) { if ( k == 0 && u == v ) return 0 ; if ( k == 1 && graph [ u ] [ v ] != INF ) return graph [ u ] [ v ] ; if ( k <= 0 ) return INF ; int res = INF ; for ( int i = 0 ; i < V ; i ++ ) { if ( graph [ u ] [ i ] != INF && u != i && v != i ) { int rec_res = shortestPath ( graph , i , v , k - 1 ) ; if ( rec_res != INF ) res = Math . min ( res , graph [ u ] [ i ] + rec_res ) ; } } return res ; } public static void main ( String [ ] args ) { int graph [ ] [ ] = new int [ ] [ ] { { 0 , 10 , 3 , 2 } , { INF , 0 , INF , 7 } , { INF , INF , 0 , 6 } , { INF , INF , INF , 0 } } ; ShortestPath t = new ShortestPath ( ) ; int u = 0 , v = 3 , k = 2 ; System . out . println ( " Weight ▁ of ▁ the ▁ shortest ▁ path ▁ is ▁ " + t . shortestPath ( graph , u , v , k ) ) ; } }