Distanzmatrix

Eine Distanzmatrix ist eine quadratische Matrix D, deren Einträge D[i,j] den Abstand zwischen den Elementen i und j einer gegebenen Menge darstellen. Typische Anwendungen finden sich bei Scheitelpunkten eines Graphen oder bei Punkten in einem metrischen Raum. Die Matrix ist in der Regel symmetrisch, D[i,i] = 0, und alle D[i,j] ≥ 0. Falls der Abstand aus einer Metrik stammt, erfüllt D die Dreiecksungleichung.

Eine Distanzmatrix lässt sich oft durch Berechnung der kürzesten Wege zwischen allen Scheitelpunkten eines gewichteten Graphen erzeugen: D[i,j] ist dann die Länge des kürzesten Pfades von i nach j. Zur Bestimmung verwendet man All-Pairs-Shortest-Paths-Algorithmen wie Floyd-Warshall oder Dijkstra mehrmals. In einem euklidischen Raum gilt D[i,j] = ||p_i − p_j||.

Es gibt Varianten und Spezialformen. Eine Euclid-Distanzmatrix stammt explizit von Punkten im Raum, eine allgemeine Distanzmatrix muss diese Struktur nicht haben. Oft spricht man auch von einer dissimilarity matrix, die nicht notwendigerweise metrische Eigenschaften erfüllt. Typische Eigenschaften sind Symmetrie, Nulldiagonale und Nichtnegativität; ob diese aus einer echten Metrik stammen, bestimmt sich nach dem konkreten Kontext.

Anwendungsgebiete reichen von Multidimensionaler Skalierung (MDS) und Clustering über phylogenetische Baumkonstruktion bis hin zur Analyse von Netzwerken und Molekülstrukturen. Distanzmatrizen dienen als Eingabe für Algorithmen, die Muster erkennen, Strukturen visualisieren oder Distanzen zwischen Objekten quantifizieren.

Beispiel: Eine Distanzmatrix für vier Objekte A, B, C, D könnte folgendermaßen aussehen:

D = [ [0,2,5,9], [2,0,3,7], [5,3,0,4], [9,7,4,0] ].