Korrektheit von Bellman-Ford-Algorithmus, können wir noch besser machen?

Question

Ich habe gelernt, dass der Bellman-Ford-Algorithmus eine Laufzeit von O (| E | * | V |) hat, in der das E die Anzahl der Kanten und der Anzahl der Scheitelpunkte ist.Angenommen, die Grafik hat keine negativ gewichteten Zyklen.

meine erste frage ist, wie beweisen wir, dass wir das in (| v | -1) nachweisen (Jede Iteration überprüft jede Kante in e), aktualisiert er den kürzesten Pfad zu jedem möglichen Knoten, wenn er einen bestimmten Startknoten auf jeden möglichen Startknoten aktualisiert?Ist es möglich, dass wir iteratiert haben (| v | -1) mal, aber immer noch nicht mit kürzesten Wegen zu jedem Knoten enden?

Nehmen wir die Richtigkeit des Algorithmus an, können wir eigentlich besser tun?Es tritt mir auf, dass nicht alle Kanten in einem bestimmten Diagramm negativ gewichtet werden.Der Bellman-Ford-Algorithmus erscheint teuer, da jede Iteration sie durch jede Kante führt.

Answer 1

Der längste mögliche Pfad von der Quelle an beliebige Änderungen würde höchstens alle anderen Scheitelpunkte in der Grafik beinhalten. Mit anderen Worten - Sie haben keinen Pfad, der mehr als einmal durch den gleichen Schäuß durchgeht, da dies notwendigerweise die Gewichte erhöht (dies ist nur dank der Tatsache, dass es keine negativen Zyklen gibt).
Bei jeder Iteration würden Sie das kürzeste Pfadgewicht auf dem nächsten SCHNITT in diesem Pfad aktualisieren, bis nach | V | -1 Iterationen Ihre Updates müssten das Ende dieses Weges erreichen. Danach gibt es keine Scheitelpunkte mit nicht engen Werten, da Ihr Update alle kürzesten Wege bis zu dieser Länge abgedeckt hat.

Diese Komplexität ist eng (zumindest für BF), denken Sie an eine lange Reihe angeschlossener Scheitelpunkte. Wählen Sie den Linksführer als Quelle - Ihr Aktualisierungsprozess müsste von dort von dort auf der anderen Seite, sobald der Schäuß bis zu einer Zeit angezeigt werden. Jetzt könnten Sie argumentieren, dass Sie nicht jede Kante auf diese Weise überprüfen müssen. Lassen Sie uns also ein paar zufällige Kanten mit einem sehr großen Gewicht werfen (N> | V | * max-Weight) - sie können Ihnen nicht helfen, aber Ihr Algorithmus kann nicht wissen, dass dies sicher ist, wenn Sie also den Prozess der Aktualisierung der Scheitelpunkte mit diesen Gewichten durchlaufen müssen (sie sind immer noch besser als die anfängliche Unendlichkeit).