Aufgabe:
1) Erweitern Sie den Moore-Bellman-Ford-Algorithmus, um in zusätzlicher Laufzeit von O(m) festzustellen, ob der Eingabegraph Kreise negativer Länge enthält.
2) Beweisen Sie die Korrektheit Ihres Verfahrens.
Problem/Ansatz:
Hinweis: Um auf die richtige Idee zu kommen, können Sie den Moore-Bellman-Ford-Algorithmus auf einem einfachen Beispiel mit negativem Kreis nachvollziehen. Was würde passieren, wenn Sie die äußere Schleife öfter als |VI - 1 mal durchlaufen würden?
