|
|
Ich habe eine Frage zu Bellman-Ford
Wenn man mit Bellman-Ford ein AllPairsShortestPath Problem löst, erhält man ja eine Distanzmatrix.
Ich soll jetzt ein Verfahren angeben, mit dem in O(n² * m), mit n Knoten und m Kanten, prüfen lässt, ob der Graph negative Zyklen enthält.
Bellman-Ford löst APSP in O(n²*m).
Sollte es einen negaiven Zyklus geben, wird in der Distanzmatrix, die Bellman-Ford erzeugt, auf der Hauptdiagonalen eine negative Distanz eingetragen sein, denn "negativer Zyklus" heisst es gibt einen Pfad (ak,...., ak) mit negativer Länge, und diese Länge wird nach n-1 Durchläufen in der Diagonalen zu finden sein.
Stimmt das so!?
Bei dem n-1 bin ich mir nicht sicher, es könnte sein, dass es einen Pfad (a1,a2,....,an) gibt, der erst mit anfügen der Kante (an,a1) negativ wird. Müsste also noch einen weiteren Durchlauf machen, glaube ich .... aber das wäre dann immernoch in O(n²*m) oder?!
Stimmt das so!?
__________________
I'm 71% Megatron!
|
|
