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 ; Given Input ; Function Call
function minDisIncludingNode ( 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 q = [ ] ; q . push ( [ 0 , 0 ] ) ; dist = new Array ( n ) . fill ( 1e9 ) ; dist [ 0 ] = 0 ; while ( q . length > 0 ) { let up = q [ 0 ] ; q . pop ( ) ; let x = up [ 0 ] ; let lev = up [ 1 ] ; if ( lev > dist [ x ] ) continue ; if ( x == n - 1 ) continue ; for ( let y of g [ x ] ) { if ( dist [ y ] > lev + 1 ) { dist [ y ] = lev + 1 ; q . push ( [ y , lev + 1 ] ) ; } } } let q1 = [ ] ; q1 . push ( [ n - 1 , 0 ] ) ; let dist1 = new Array ( n ) . fill ( 1e9 ) ; dist1 [ n - 1 ] = 0 ; while ( q1 . length > 0 ) { let up = q1 [ 0 ] ; q1 . pop ( ) ; let x = up [ 0 ] ; let lev = up [ 1 ] ; if ( lev > dist1 [ x ] ) continue ; if ( x == 0 ) continue ; for ( let y of g [ x ] ) { if ( dist1 [ y ] > lev + 1 ) { dist1 [ y ] = lev + 1 ; q1 . push ( [ y , lev + 1 ] ) ; } } } for ( let i = 0 ; i < n ; i ++ ) { if ( dist [ i ] + dist1 [ i ] > 1e9 ) document . write ( - 1 + " " ) ; else document . write ( dist [ i ] + dist1 [ i ] + " " ) ; } } let n = 5 ; let m = 7 ; let edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 5 ] , [ 4 , 3 ] , [ 4 , 5 ] , [ 1 , 5 ] , ] ; minDisIncludingNode ( n , m , edges ) ;