protected void reduce ( ) { for ( int w = 0 ; w < dim ; w ++ ) { double min = Double . POSITIVE_INFINITY ; for ( int j = 0 ; j < dim ; j ++ ) { if ( costMatrix [ w ] [ j ] < min ) { min = costMatrix [ w ] [ j ] ; } } for ( int j = 0 ; j < dim ; j ++ ) { costMatrix [ w ] [ j ] -= min ; } } double [ ] min = new double [ dim ] ; for ( int j = 0 ; j < dim ; j ++ ) { min [ j ] = Double . POSITIVE_INFINITY ; } for ( int w = 0 ; w < dim ; w ++ ) { for ( int j = 0 ; j < dim ; j ++ ) { if ( costMatrix [ w ] [ j ] < min [ j ] ) { min [ j ] = costMatrix [ w ] [ j ] ; } } } for ( int w = 0 ; w < dim ; w ++ ) { for ( int j = 0 ; j < dim ; j ++ ) { costMatrix [ w ] [ j ] -= min [ j ] ; } } }
Reduce the cost matrix by subtracting the smallest element of each row from all elements of the row as well as the smallest element of each column from all elements of the column . Note that an optimal assignment for a reduced cost matrix is optimal for the original cost matrix .