Obteniendo un ciclo negativo usando Bellman Ford

Tengo que encontrar un ciclo negativo en un gráfico ponderado dirigido. Sé cómo funciona el algoritmo Bellman Ford, y que me dice si hay un ciclo negativo alcanzable. Pero no lo nombra explícitamente.

¿Cómo puedo obtener la ruta real del ciclo?$v1, v2, \ldots vk, v1$

Después de aplicar el algoritmo estándar, ya hicimos iteraciones y no debería ser posible ninguna mejora adicional. Si aún podemos reducir la distancia a un nodo, existe un ciclo negativo.$n-1$

Mi idea es: dado que conocemos el borde que aún puede mejorar el camino y conocemos el predecesor de cada nodo, podemos rastrear nuestro camino desde ese borde hasta que lo encontremos nuevamente. Ahora deberíamos tener nuestro ciclo.

Lamentablemente, no encontré ningún documento que me diga si esto es correcto. Entonces, ¿realmente funciona así?

Editar: este ejemplo demuestra que mi idea es incorrecta. Dado el siguiente gráfico, ejecutamos Bellman-Ford desde el nodo .$1$

Procesamos aristas en el orden . Después de n - 1 iteraciones obtenemos distancias de nodo: 1 : - 5 2 : - 30 3 : - $a, b, c, d$$n-1$
$1: -5$
$2: -30$
$3: -15$

y tabla padre:
tiene padre 3 2 tiene padre 3 3 tiene padre $1$$3$
$2$$3$
$3$$2$

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

$c, d$$a$

¿Cómo podemos resolver este problema?

$v_1$

$s$

Su ejemplo no contradice su idea. De hecho, has encontrado un ciclo negativo. Creo que la idea que ilustra su ejemplo es que el vértice de origen podría no ser un nodo en el ciclo negativo.