Fürchtet sich Minimum Spanning Tree vor negativen Gewichten?

Dies ist ein follow-up-Frage der Warum die meisten Graphen algorithmen nicht anpassen, so leicht zu negativen zahlen?.

Ich denke Shortest Path (SP) hat problem mit negativen gewichten, denn es summiert alle GEWICHTE entlang der Pfade und versucht zu finden, die minimale.

Aber ich glaube nicht, Minimum Spanning Tree (MST) hat Probleme mit negativen gewichten, weil es nur nimmt, der minimales Gewicht Rand, ohne sich um die Gesamtsumme der GEWICHTE.

Habe ich Recht?

InformationsquelleAutor der Frage Jackson Tale | 2012-05-02

  1. 46

    Ja, du hast Recht. Das Konzept des MST können GEWICHTE von einem beliebigen Zeichen. Die zwei bekanntesten algorithmen zum Auffinden von MST (Kruskal und Prim), funktioniert mit negativen Kanten.

    Tatsächlich ist, können Sie fügen Sie einfach eine große positive Konstante zu allen Kanten des Graphen, so dass alle Kanten positive. Die MST (als Teilmenge der Kanten) wird die gleiche bleiben.

    InformationsquelleAutor der Antwort Skiminok

  2. 1

    Ja, du hast Recht, weil wenn Sie sehen, dass der Algorithmus für kürzeste Pfad wie dijkstera es wird überprüft, ob der gegenwärtige Abstand der Knoten v ist größer als die Summe des Barwerts + edge Gewicht dann ändert es den Wert der Distanz von Knoten v aus s, indem die Summe Wert und wenn das edge-Gewicht ist negativ, dann gibt es einige Probleme.

    Aber in der MST-problem, gibt es algorithmen wie prims,kruskal, die nur das minimale Gewicht Rand, so dass das negative edge qualifizieren sich für die MST.

    InformationsquelleAutor der Antwort Rahul Dhawan

Schreibe einen Kommentar