Number of minimum length paths between 1 to N including each node | Function to calculate the distances from node 1 to N ; Stores the number of edges ; Storing the edges in vector ; Initialize queue ; BFS from 1 st node using queue ; Pop from queue ; Traversing the adjacency list ; Initialize queue ; BFS from last node ; Pop from queue ; Traverse the adjacency list ; Print the count of minimum distance ; Driver Code
def countMinDistance ( 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 queue1 = [ ] NEW_LINE queue1 . append ( [ 0 , 0 ] ) NEW_LINE dist = [ 1e9 for i in range ( n ) ] NEW_LINE ways1 = [ 0 for i in range ( n ) ] NEW_LINE dist [ 0 ] = 0 NEW_LINE ways1 [ 0 ] = 1 NEW_LINE while ( len ( queue1 ) > 0 ) : NEW_LINE INDENT up = queue1 [ 0 ] NEW_LINE queue1 = queue1 [ : - 1 ] NEW_LINE x = up [ 0 ] NEW_LINE dis = up [ 1 ] NEW_LINE if ( dis > 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 ] > dis + 1 ) : NEW_LINE INDENT dist [ y ] = dis + 1 NEW_LINE ways1 [ y ] = ways1 [ x ] NEW_LINE queue1 . append ( [ y , dis + 1 ] ) NEW_LINE DEDENT elif ( dist [ y ] == dis + 1 ) : NEW_LINE INDENT ways1 [ y ] += ways1 [ x ] NEW_LINE DEDENT DEDENT DEDENT queue2 = [ ] NEW_LINE queue2 . append ( [ n - 1 , 0 ] ) NEW_LINE dist1 = [ 1e9 for i in range ( n ) ] NEW_LINE ways2 = [ 0 for i in range ( n ) ] NEW_LINE dist1 [ n - 1 ] = 0 NEW_LINE ways2 [ n - 1 ] = 1 NEW_LINE while ( len ( queue2 ) > 0 ) : NEW_LINE INDENT up = queue2 [ 0 ] NEW_LINE queue2 = queue2 [ : - 1 ] NEW_LINE x = up [ 0 ] NEW_LINE dis = up [ 1 ] NEW_LINE if ( dis > 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 ] > dis + 1 ) : NEW_LINE INDENT dist1 [ y ] = dis + 1 NEW_LINE ways2 [ y ] = ways2 [ x ] NEW_LINE queue2 . append ( [ y , dis + 1 ] ) NEW_LINE DEDENT elif ( dist1 [ y ] == 1 + dis ) : NEW_LINE INDENT ways2 [ y ] += ways2 [ x ] NEW_LINE DEDENT DEDENT DEDENT ways1 [ n - 1 ] = 1 NEW_LINE ways2 [ n - 1 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( ways1 [ i ] * ways2 [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE M = 5 NEW_LINE edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 1 , 3 ] , [ 2 , 5 ] , [ 2 , 4 ] ] NEW_LINE countMinDistance ( N , M , edges ) NEW_LINE DEDENT