Find if there is a path between two vertices in a directed graph | Set 2 | Python3 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 code
X = 6 NEW_LINE Z = 2 NEW_LINE def existPath ( V , edges , u , v ) : NEW_LINE INDENT mat = [ [ False for i in range ( V ) ] for j in range ( V ) ] NEW_LINE for i in range ( X ) : NEW_LINE INDENT mat [ edges [ i ] [ 0 ] ] [ edges [ i ] [ 1 ] ] = True NEW_LINE DEDENT for k in range ( V ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT mat [ i ] [ j ] = ( mat [ i ] [ j ] or mat [ i ] [ k ] and mat [ k ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT if ( u >= V or v >= V ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( mat [ u ] [ v ] ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT V = 4 NEW_LINE edges = [ [ 0 , 2 ] , [ 0 , 1 ] , [ 1 , 2 ] , [ 2 , 3 ] , [ 2 , 0 ] , [ 3 , 3 ] ] NEW_LINE u , v = 1 , 3 NEW_LINE if ( existPath ( V , edges , u , v ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT