Sorting arr based on score matrix

  adjacency-matrix, c++, graph, sorting

I need to find the best sorted array,
given an array of consecutive integers that start from 0
and a symmetric matrix describing at every position the array items scores.
matrix[row][col] is the score of items row and col in the given array.
the matrix is like an adjacency matrix but with similarity scores.
for example:
arr is {0, 1, 2, 3}

and the matrix is:

int [] matrix = {{0  , 250, 50 , 150},
 {250, 0  , 0  , 120},
 {50 , 0  , 0  , 500},
 {150, 120, 500, 0  }}

score of 0 and 1 is 250
score of 0 and 2 is 50
score of 0 and 3 is 150
score of 1 and 3 is 120
score of 2 and 3 is 500

so the best "sorted" arr is {2, 3, 0 ,1}

Constraints:
There may be elements that should be removed from the array

I tried to convert the matrix to 1 and 0 matrix with some threshold, and then to use cuthill-mckee algorithm.
the results where mediocre.

Source: Windows Questions C++

LEAVE A COMMENT