Finden eines entsprechenden Graphen aus gegebenen kürzesten Wegen

Question

Gegeben n von n Punkten und dem Abstand d zwischen diesen Punkten muss ich den entsprechenden ungerichteten gewichteten Graphen finden, der diese Abstände ergeben würde. Ich habe versucht, den Algorithmus von Prim zu verwenden, um die MST zu finden, aber dieser Satz hat die Größe n-1 und enthält nicht die n benötigten Kanten. Z.B. n durch n Entfernungen gegeben

0 3 5 
3 0 4 
5 4 0 

Ich brauche die entsprechenden Kanten zu finden:

1 - 2 = 3 
1 - 3 = 5 
2 - 3 = 4 

, die in der graphischen Darstellung ergibt:

 3 
1 --------- 2 
\  /
    \5  /4 
    \ /
    \ /
     3 

jedoch Prim zurückkehren würde nur die ersten zwei Kanten seit Eine MST enthält keine Zyklen.

Answer 1

Ein Graph, der zu diesen Abständen führen würde, ist der Graph, der eine Kante von jedem Knoten zu jedem anderen Knoten hat und die Länge dieser Kante ist der Abstand gemäß der Matrix. (Ich bin mir nicht sicher, was Sie mit ungewichtetem gemeint haben, weil das Beispiel, das Sie geben, ungerichtet zu sein scheint und ich bin mir nicht sicher, was der Unterschied zwischen Gewichten und Längen hier ist). Eine andere Möglichkeit wäre, die Abstände in aufsteigender Reihenfolge zu betrachten, wie Sie es mit Prims Algorithmus getan haben, und neben der Überprüfung, ob die Kante für die Verbindung der beiden Enden benötigt wird, prüfen Sie, ob der Mindestabstand vorhanden ist zwischen diesen Enden in der Grafik rekonstruiert ist so weit wie der Abstand in der Matrix. Wenn dies nicht der Fall ist, fügen Sie die Kante hinzu, auch wenn die Enden in der Grafik so weit verbunden sind.