Warum negative Kante in Bellman Ford Algorithmen erlaubt?

Question

warum negative Kanten Zyklen in Bellman Ford Algorithmen erlaubt sind, während keine negative Kante in Dijkstra Algorithmen erlaubt?

Answer 1

Alle Ihre Fragen scheinen bis zum Klassenzimmer Fragen zu sein. Siehe 1.) Lehrbuch und 2.) Klassennotizen. Sie werden die Antwort entweder an einer oder an beiden Stellen deutlich dokumentiert finden.

Answer 2

Erlaubt? Bellman-Ford-Algorithmus ermöglicht ausgeprägte Kanten mit negativen Gewichtungen (nicht im Dijkstra-Algorithmus unterstützt), aber keiner der beiden Algorithmen "erlaubt" negative Zyklen. Das kürzeste Pfadproblem ergibt keinen Sinn in Anwesenheit eines negativen Zyklus, so dass es keinen sinnvollen Weg gibt, negative Zyklen in einem solchen Algorithmus zu "erlauben".

Der Bellman-Ford-Algorithmus kann dazu verwendet werden, das Vorhandensein eines negativen Zyklus zu erkennen und die Ausführung abzubrechen (Abbruch, da in diesem Fall keine korrekte Lösung existiert).