Minimum length paths between 1 to N including each node | Function to calculate the distances from node 1 to N ; Vector to store our edges ; Storing the edgees in the Vector ; Initialize queue ; BFS from first node using queue ; Pop from queue ; Traversing its adjacency list ; Initialize queue ; BFS from last node using queue ; Pop from queue ; Traversing its adjacency list ; Printing the minimum distance including node i ; If not reachable ; Path exists ; Driver Code ; Given Input ; Function Call
def minDisIncludingNode ( n , m , edges ) : NEW_LINE INDENT g = [ [ ] for i in range ( 10005 ) ] NEW_LINE for i in range ( m ) : NEW_LINE INDENT a = edges [ i ] [ 0 ] - 1 NEW_LINE b = edges [ i ] [ 1 ] - 1 NEW_LINE g [ a ] . append ( b ) NEW_LINE g [ b ] . append ( a ) NEW_LINE DEDENT q = [ ] NEW_LINE q . append ( [ 0 , 0 ] ) NEW_LINE dist = [ 1e9 for i in range ( n ) ] NEW_LINE dist [ 0 ] = 0 NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT up = q [ 0 ] NEW_LINE q = q [ 1 : ] NEW_LINE x = up [ 0 ] NEW_LINE lev = up [ 1 ] NEW_LINE if ( lev > dist [ x ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( x == n - 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for y in g [ x ] : NEW_LINE INDENT if ( dist [ y ] > lev + 1 ) : NEW_LINE INDENT dist [ y ] = lev + 1 NEW_LINE q . append ( [ y , lev + 1 ] ) NEW_LINE DEDENT DEDENT DEDENT q1 = [ ] NEW_LINE q1 . append ( [ n - 1 , 0 ] ) NEW_LINE dist1 = [ 1e9 for i in range ( n ) ] NEW_LINE dist1 [ n - 1 ] = 0 NEW_LINE while ( len ( q1 ) > 0 ) : NEW_LINE INDENT up = q1 [ 0 ] NEW_LINE q1 = q1 [ 1 : ] NEW_LINE x = up [ 0 ] NEW_LINE lev = up [ 1 ] NEW_LINE if ( lev > dist1 [ x ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( x == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for y in g [ x ] : NEW_LINE INDENT if ( dist1 [ y ] > lev + 1 ) : NEW_LINE INDENT dist1 [ y ] = lev + 1 NEW_LINE q1 . append ( [ y , lev + 1 ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( dist [ i ] + dist1 [ i ] > 1e9 ) : NEW_LINE INDENT print ( - 1 , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( dist [ i ] + dist1 [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE m = 7 NEW_LINE edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 5 ] , [ 4 , 3 ] , [ 4 , 5 ] , [ 1 , 5 ] ] NEW_LINE minDisIncludingNode ( n , m , edges ) NEW_LINE DEDENT