Dijkstra geht davon aus, dass die Kosten für Pfade montonisch steigen. Das plus die geordnete Suche (mit der Prioritätswarteschlange) bedeutet, dass Sie, wenn Sie zum ersten Mal einen Knoten erreichen, auf dem kürzesten Weg angekommen sind.
Dies gilt nicht für negative Gewichtungen. Wenn Sie dijkstra mit negativen Gewichtungen verwenden, dann können Sie feststellen, dass ein späterer Pfad besser ist als ein früherer Pfad (weil eine negative Gewichtung den Pfad in einem späteren Schritt verbessert hat).
so in bellman-ford, wenn Sie an einem Knoten ankommen, den Sie testen, um zu sehen, ob der neue Pfad kürzer ist. im Gegensatz dazu, mit Dijkstra, können Sie Knoten
in einigen (die meisten) Fälle clipling werden Dijkstra wird nicht alle vollständigen Pfade erkunden. zum Beispiel, wenn G nur zurück zu C verbunden wäre, wäre jeder Pfad durch G höhere Kosten, als dass jeder durch C. bellman-ford immer noch alle Pfade durch G zu F betrachten würde (dijkstra würde diese niemals betrachten, da sie höhere Kosten haben durch C gehen). Wenn es dies nicht tut, kann es keine negativen Schleifen finden.
Hier ist ein Beispiel: die oben genannten berechnet nie den Pfad AGEF. E ist bereits markiert, wie durch die Zeit, die Sie von G. ankommen besuchte
Unterschied zwischen DIjkstra und BellmanFord Algorithmus
IFRC Bellman-Ford verwaltet auch Bogen mit negativen Kosten – BigMike
Aber wenn ich Visualisierung machen möchte, so für Bellman-Ford, würde es gleich aussehen? – Wish
Sie können B-F mit verschiedenen Graphen mit negativen Werten anzeigen. Aber für Dijkstra kann man das nicht benutzen. – shan