Mit Bellman Ford einen negativen Zyklus bekommen

20

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?v1,v2,vk,v1

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.n1

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 .1

Bildbeschreibung hier eingeben

Wir verarbeiten Kanten in der Reihenfolge . Nach n - 1 Iterationen erhalten wir Knotenabstände: 1 : - 5 2 : - 30 3a,b,c,dn1
1:5
2:-30
3:-15

und Elterntabelle:
hat Eltern 3 2 hat Eltern 3 3 hat Eltern 213
23
32

n1aa

Wenn wir uns jedoch auf dem Rückweg durch die übergeordnete Tabelle befinden, bleiben wir in einem weiteren negativen Zyklus steckenc,da

Wie können wir dieses Problem lösen?

Patrick Schmidt
quelle

Antworten:

14

v1

Eine einfache Google-Suche ergibt Xiuzhen Huang:s

Paresh
quelle
Verbindung ist unterbrochen.
human.js
Ich habe gerade die Idee von Prof. Huang verwendet, aber ich verstehe nicht, warum er sowohl einen neuen Quellknoten als auch ein neues Ziel ( s'und t') 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.
AbuNassar
0

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.

Spartan 117
quelle