Find if there is a path between two vertices in a directed graph | Set 2 | C ++ 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 ; dp matrix ; set dp [ 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 function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define X  6 NEW_LINE #define Z  2 NEW_LINE bool existPath ( int V , int edges [ X ] [ Z ] , int u , int v ) { bool mat [ V ] [ V ] ; memset ( mat , false , sizeof ( mat ) ) ; 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 ; } int main ( ) { int V = 4 ; int edges [ X ] [ Z ] = { { 0 , 2 } , { 0 , 1 } , { 1 , 2 } , { 2 , 3 } , { 2 , 0 } , { 3 , 3 } } ; int u = 1 , v = 3 ; if ( existPath ( V , edges , u , v ) ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; return 0 ; }