Minimum steps required to convert X to Y where a binary matrix represents the possible conversions | Pyton3 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
INF = 99999 NEW_LINE size = 10 NEW_LINE def findMinimumSteps ( mat , x , y , n ) : NEW_LINE INDENT dist = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE i , j , k = 0 , 0 , 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 0 ) : NEW_LINE INDENT dist [ i ] [ j ] = INF NEW_LINE DEDENT else : NEW_LINE INDENT dist [ i ] [ j ] = 1 NEW_LINE DEDENT if ( i == j ) : NEW_LINE INDENT dist [ i ] [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT for k in range ( n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) : NEW_LINE INDENT dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( dist [ x ] [ y ] < INF ) : NEW_LINE INDENT return dist [ x ] [ y ] NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT 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 ] ] NEW_LINE x , y = 2 , 3 NEW_LINE print ( findMinimumSteps ( mat , x , y , size ) ) NEW_LINE