Ich weiß, dass es keine Methode gibt, Mindestabstand zu finden, wenn es negative Gewichtungszyklen in einem Diagramm gibt, gibt es keine Bedeutung des Mindestabstandes. Meine Frage ist, was passiert, wenn wir Floyd Warshall Algorithmus mit Graphen mit negativen Gewichtszyklen füttern? Wird es unbegrenzt laufen oder terminieren (vielleicht mit falscher Antwort) in O (n)?Zeit Komplexität von Floyd Warshall Algorithmus auf negative Gewichtszyklen
Wie Sie auf Wikipedia finden können
Es gibt keine Bedingungen in Floyd-Warshall-Algorithmen, die auf aktuellem Gewicht oder maximalem Gewicht basieren.
Algorithmen durchlaufen einfach alle Knotenpaare und berechnen die Entfernung. Also die Antwort ist Nein, es wird nicht unbegrenzt laufen.
Und definitiv Algorithmus wird falsche Antwort zurückgeben (für Ecken in negativen Zyklen haben Sie negative Abstände). Zum Beispiel wäre die Entfernung vom Scheitelpunkt zu sich negativ.
Auch dieser Algorithmus kann auch für die Erkennung negativer Zyklen verwendet werden.