Mendapatkan siklus negatif menggunakan Bellman Ford

Saya harus menemukan siklus negatif dalam grafik tertimbang yang diarahkan. Saya tahu bagaimana algoritma Bellman Ford bekerja, dan ia memberi tahu saya jika ada siklus negatif yang dapat dijangkau. Tetapi tidak secara eksplisit menyebutkannya.

Bagaimana saya bisa mendapatkan jalur aktual dari siklus?$v1, v2, \ldots vk, v1$

Setelah menerapkan algoritma standar kami sudah melakukan iterasi dan tidak ada perbaikan lebih lanjut yang mungkin dilakukan. Jika kita masih bisa menurunkan jarak ke sebuah simpul, ada siklus negatif.$n-1$

Ide saya adalah: Karena kita tahu tepi yang masih bisa memperbaiki jalur dan kita tahu pendahulu setiap node, kita bisa melacak jalan kita kembali dari tepi itu sampai kita bertemu lagi. Sekarang kita harus memiliki siklus kita.

Sayangnya, saya tidak menemukan kertas yang memberi tahu saya apakah ini benar. Jadi, apakah ini benar-benar berfungsi seperti itu?

Sunting: Contoh ini membuktikan bahwa ide saya salah. Diberikan grafik berikut, kami menjalankan Bellman-Ford dari node .$1$

Kami memproses tepian dalam urutan . Setelah n - 1 iterasi kami mendapatkan jarak simpul: 1 : - 5 2 : - 30 3 : - $a, b, c, d$$n-1$
$1: -5$
$2: -30$
$3: -15$

dan tabel induk:
memiliki induk 3 2 memiliki induk 3 3 memiliki induk $1$$3$
$2$$3$
$3$$2$

$n$$1$$a$$a$

$c, d$$a$

Bagaimana kita bisa menyelesaikan masalah ini?

$v_1$

$s$

Teladan Anda tidak bertentangan dengan ide Anda. Memang Anda telah menemukan siklus negatif. Saya pikir ide contoh Anda menggambarkan bahwa sumber simpul mungkin bukan simpul dalam siklus negatif.