Minimum steps required to convert X to Y where a binary matrix represents the possible conversions | JavaScript implementation of the above approach ; dist will be the output matrix that will finally have the shortest distances between every pair of numbers ; Initially same as mat ; Add all numbers one by one to the set of intermediate numbers . Before start of an iteration , we have shortest distances between all pairs of numbers such that the shortest distances consider only the numbers in set { 0 , 1 , 2 , . . k - 1 } as intermediate numbers . After the end of an iteration , vertex no . k is added to the set of intermediate numbers and the set becomes { 0 , 1 , 2 , . . k } ; Pick all numbers as source one by one ; Pick all numbers as destination for the above picked source ; If number k is on the shortest path from i to j , then update the value of dist [ i ] [ j ] ; If no path ; Driver Code
var INF = 99999 ; function findMinimumSteps ( mat , x , y , n ) { var i , j , k ; var dist = Array ( n ) . fill ( ) . map ( ( ) => Array ( n ) . fill ( 0 ) ) ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) dist [ i ] [ j ] = INF ; else dist [ i ] [ j ] = 1 ; if ( i == j ) dist [ i ] [ j ] = 1 ; } } for ( k = 0 ; k < n ; k ++ ) { for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] ; } } } if ( dist [ x ] [ y ] < INF ) return dist [ x ] [ y ] ; else return - 1 ; } var mat = [ [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 ] ] ; var x = 2 , y = 3 ; var size = mat . length ; document . write ( findMinimumSteps ( mat , x , y , size ) ) ;