Wenn ich kürzeste Pfade von einer Quelle zu allen anderen Knoten in der Grafik finden muss, die sowohl gerichtet als auch gewichtet ist, kann ich den Dijkstras-Algorithmus verwenden oder muss ich den BellFord-Algorithmus verwenden?Dijkstra vs BellFord Algorithmus
Da eine korrekte Implementierung von Dijkstra schneller als Bellman-Ford ist, verwenden Sie Dijkstra, es sei denn, es gibt negative Gewichtungskanten im Diagramm. In diesem Fall kann Dijkstra falsch sein, aber Bellman-Ford gibt immer noch die richtige Antwort zurück.
Denken Sie daran, dass, wenn ein Graph einen negativen Gewichtszyklus hat, der kürzeste Pfad nicht gut definiert ist. Bellman-Ford kann modifiziert werden, um prüfen zu können, ob ein bestimmter Graph einen negativen Gewichtszyklus hat.
Ford kann mit negativen Gewichten umgehen, Dijkstra kann nicht. Verwenden Sie Ford, wenn es welche gibt – Idos