Ich muss einen negativen Zyklus in einem gerichteten gewichteten Graphen finden. Ich weiß, wie der Bellman Ford-Algorithmus funktioniert und ob es einen erreichbaren negativen Zyklus gibt. Es nennt es aber nicht explizit.
Wie kann ich den tatsächlichen Pfad des Zyklus erhalten?
Nachdem wir den Standardalgorithmus angewendet haben, haben wir bereits Iterationen durchgeführt und es sollte keine weitere Verbesserung möglich sein. Wenn wir den Abstand zu einem Knoten noch verringern können, liegt ein negativer Zyklus vor.
Meine Idee ist: Da wir den Rand kennen, der den Pfad noch verbessern kann, und den Vorgänger jedes Knotens kennen, können wir unseren Weg von diesem Rand zurückverfolgen, bis wir ihn wieder treffen. Jetzt sollten wir unseren Zyklus haben.
Leider habe ich kein Papier gefunden, aus dem hervorgeht, ob dies korrekt ist. Funktioniert es also tatsächlich so?
Bearbeiten: Dieses Beispiel zeigt, dass meine Idee falsch ist. In der folgenden Grafik führen wir Bellman-Ford vom Knoten aus .
Wir verarbeiten Kanten in der Reihenfolge . Nach n - 1 Iterationen erhalten wir Knotenabstände: 1 : - 5 2 : - 30 3
und Elterntabelle:
hat Eltern 3 2 hat Eltern 3 3 hat Eltern 2
Wenn wir uns jedoch auf dem Rückweg durch die übergeordnete Tabelle befinden, bleiben wir in einem weiteren negativen Zyklus stecken
Wie können wir dieses Problem lösen?
quelle
s'
undt'
) hinzufügt . Es schien mir, als würde ein neuer Quellknoten, der durch eine beliebige Kante mit allen vorhandenen Scheitelpunkten verbunden ist, alle Zyklen auftauchen lassen.Ihr Beispiel widerspricht nicht Ihrer Vorstellung. In der Tat haben Sie einen negativen Zyklus gefunden. Ich denke, die Idee, die Ihr Beispiel veranschaulicht, ist, dass der Quellscheitelpunkt möglicherweise kein Knoten im negativen Zyklus ist.
quelle