Bellman Ford-Algorithmus mit negativen Zyklen

Question

Also, wenn ich versuche, den kürzesten Weg mit Bellman Ford-Algorithmus mit dieser Methode zu testen, um herauszufinden, ob es einen Weg:

public boolean hasPath(int v){ 
    return distTo[v] < Double.POSITIVE_INFINITY; 
} 

Wenn ich einen negativen Zyklus haben dann was passiert mit diesem Algorithmus? Trifft es immer noch zu, weil ich weiß, dass Dijkstras Algorithmus nicht mit negativen Zyklen arbeitet, aber was ist mit Ford?

Answer 1

Es wird funktionieren, aber der Wert möglicherweise oder nicht der kürzeste Pfad sein. Der tatsächliche kürzeste Pfad kann tatsächlich eine negative Unendlichkeit sein, da, wenn der negative Kreis den Zielknoten erreicht, immer ein kürzerer Pfad als der momentan kürzeste Pfad vorhanden ist.

So verwenden Sie Bellman-Ford, um negative Kreise zu erkennen. Wenn nach | V | Schleifen, der (| V | +1) th aktualisiert immer noch den kürzesten Weg, es gibt einen negativen Kreis im Graphen.