Issue with affinity propagation and dtype np.float32

[glemaitre]

While working on #23838, it seems that the issue observed in #10832 was not solved since it breaks for different random seeds.

Therefore, we should revisit the original issue.

[jeremiedbb]

The snippet reported in #10832

import sklearn.cluster
import numpy as np

k = np.array([[1,0,0,0],
              [0,1,1,0],
              [0,1,1,0],
              [0,0,0,1]], dtype='float32')

afp = sklearn.cluster.AffinityPropagation(preference=1, affinity='precomputed').fit(k)
print(afp.labels_)

expects 3 clusters, with labels [0,1,1,2]. It actually has nothing to do with float32 or float64: it breaks for some random seeds whether k is float64 or float32.

I'm not familiar with this estimator so I don't know if this clustering should be expected regardless of the noise added during fit.