Uzyskiwanie ujemnego cyklu za pomocą Bellmana Forda

Muszę znaleźć cykl ujemny na ukierunkowanym wykresie ważonym. Wiem, jak działa algorytm Bellmana Forda i który mówi mi, czy istnieje możliwy do osiągnięcia cykl ujemny. Ale nie określa go wprost.

Jak uzyskać rzeczywistą ścieżkę cyklu?$v1, v2, \ldots vk, v1$

Po zastosowaniu standardowego algorytmu wykonaliśmy już iteracji i dalsza poprawa nie powinna być możliwa. Jeśli nadal możemy obniżyć odległość do węzła, istnieje cykl ujemny.$n-1$

Mój pomysł jest następujący: ponieważ znamy krawędź, która wciąż może poprawić ścieżkę i znamy poprzednika każdego węzła, możemy prześledzić drogę powrotną od tej krawędzi, dopóki nie spotkamy się ponownie. Teraz powinniśmy mieć nasz cykl.

Niestety nie znalazłem żadnego dokumentu, który powiedziałby mi, czy to prawda. Czy to naprawdę tak działa?

Edycja: Ten przykład dowodzi, że mój pomysł jest błędny. Biorąc pod uwagę poniższy wykres, uruchamiamy Bellman-Ford od węzła .$1$

Krawędzie przetwarzamy w kolejności . Po n - 1 iteracjach otrzymujemy odległości między węzłami: 1 : - 5 2 : - 30 3 : - $a, b, c, d$$n-1$
$1: -5$
$2: -30$
$3: -15$

a tabela nadrzędna:
ma nadrzędny 3 2 ma nadrzędny 3 3 ma nadrzędny $1$$3$
$2$$3$
$3$$2$

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

$c, d$$a$

Jak możemy rozwiązać ten problem?

$v_1$

$s$

Twój przykład nie jest sprzeczny z twoim pomysłem. Rzeczywiście znalazłeś cykl ujemny. Myślę, że ideą, którą ilustruje twój przykład, jest to, że wierzchołek źródłowy może nie być węzłem w cyklu ujemnym.