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
function countMinDistance ( n , m , edges ) { let g = new Array ( 10005 ) . fill ( 0 ) . map ( ( ) => [ ] ) ; for ( let i = 0 ; i < m ; i ++ ) { let a = edges [ i ] [ 0 ] - 1 ; let b = edges [ i ] [ 1 ] - 1 ; g [ a ] . push ( b ) ; g [ b ] . push ( a ) ; } let queue1 = [ ] ; queue1 . push ( [ 0 , 0 ] ) ; let dist = new Array ( n ) . fill ( 1e9 ) ; let ways1 = new Array ( n ) . fill ( 0 ) ; dist [ 0 ] = 0 ; ways1 [ 0 ] = 1 ; while ( queue1 . length > 0 ) { let up = queue1 [ 0 ] ; queue1 . pop ( ) ; let x = up [ 0 ] ; let dis = up [ 1 ] ; if ( dis > dist [ x ] ) continue ; if ( x == n - 1 ) continue ; for ( let y of g [ x ] ) { if ( dist [ y ] > dis + 1 ) { dist [ y ] = dis + 1 ; ways1 [ y ] = ways1 [ x ] ; queue1 . push ( [ y , dis + 1 ] ) ; } else if ( dist [ y ] == dis + 1 ) ways1 [ y ] += ways1 [ x ] ; } } let queue2 = [ ] ; queue2 . push ( [ n - 1 , 0 ] ) ; let dist1 = new Array ( n ) . fill ( 1e9 ) ; let ways2 = new Array ( n ) . fill ( 0 ) ; dist1 [ n - 1 ] = 0 ; ways2 [ n - 1 ] = 1 ; while ( queue2 . length > 0 ) { let up = queue2 [ 0 ] ; queue2 . pop ( ) ; let x = up [ 0 ] ; let dis = up [ 1 ] ; if ( dis > dist1 [ x ] ) continue ; if ( x == 0 ) continue ; for ( let y of g [ x ] ) { if ( dist1 [ y ] > dis + 1 ) { dist1 [ y ] = dis + 1 ; ways2 [ y ] = ways2 [ x ] ; queue2 . push ( [ y , dis + 1 ] ) ; } else if ( dist1 [ y ] == 1 + dis ) ways2 [ y ] += ways2 [ x ] ; } } ways1 [ n - 1 ] = 1 ; ways2 [ n - 1 ] = 1 ; for ( let i = 0 ; i < n ; i ++ ) document . write ( ways1 [ i ] * ways2 [ i ] + " " ) ; } let N = 5 ; let M = 5 ; let edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 1 , 3 ] , [ 2 , 5 ] , [ 2 , 4 ] , ] ; countMinDistance ( N , M , edges ) ;