Negativer Zyklus
Definition
Ein negativer Zyklus hat eine Summe seiner Kantengewichte unter null.
In einem gewichteten Graphen kann wiederholtes Durchlaufen eines erreichbaren negativen Zyklus die Gesamtkosten immer weiter senken. Dann existiert für betroffene Wege kein endlicher kürzester Wert.
Einfach erklärt
Ein Rundweg zieht bei jeder Runde weitere Punkte vom Wegpreis ab.
Warum das im Alltag wichtig ist
Das ist bei Kürzeste-Wege-Verfahren und Konsistenzprüfungen wichtig.
Beispiel aus dem Mittelstand
Fiktiv: Ein Planungsmodell entdeckt widersprüchliche Kosten über einen Rundweg.
Grenzen und Fallstricke
- Nicht jede negative Kante bildet einen negativen Zyklus. Erreichbarkeit und Zielbezug müssen berücksichtigt werden.
Entstehung & Geschichte
Der Begriff gehört zur Graphentheorie und zu Algorithmen wie Bellman-Ford.
Anwendung im Mittelstand
- KMU können damit Fehler in gewichteten Planungs- oder Optimierungsmodellen erkennen.
Häufige Fragen
Kann Dijkstra negative Zyklen korrekt behandeln?
Dafür ist das Verfahren nicht ausgelegt.
Quellen
- negative_edge_cycle — · NetworkX: negative_edge_cycle —
Redaktionell geprüft am: