Find if there is a path between two vertices in a directed graph | Set 2 | Java program to find if there is a path between two vertices in a directed graph using Dynamic Programming ; Function to find if there is a path between two vertices in a directed graph ; mat matrix ; set mat [ i ] [ j ] = true if there is edge between i to j ; Check for all intermediate vertex ; If vertex is invalid ; If there is a path ; Driver code
import java . util . * ; class GFG { static final int X = 6 ; static final int Z = 2 ; static boolean existPath ( int V , int edges [ ] [ ] , int u , int v ) { boolean [ ] [ ] mat = new boolean [ V ] [ V ] ; for ( int i = 0 ; i < X ; i ++ ) mat [ edges [ i ] [ 0 ] ] [ edges [ i ] [ 1 ] ] = true ; for ( int k = 0 ; k < V ; k ++ ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { mat [ i ] [ j ] = mat [ i ] [ j ] || mat [ i ] [ k ] && mat [ k ] [ j ] ; } } } if ( u >= V v >= V ) { return false ; } if ( mat [ u ] [ v ] ) return true ; return false ; } public static void main ( String [ ] args ) { int V = 4 ; int edges [ ] [ ] = { { 0 , 2 } , { 0 , 1 } , { 1 , 2 } , { 2 , 3 } , { 2 , 0 } , { 3 , 3 } } ; int u = 1 , v = 3 ; if ( existPath ( V , edges , u , v ) ) System . out . print ( "YesNEW_LINE"); else System . out . print ( "NoNEW_LINE"); } }