how to print a negative cycle in a graph G?
<p>how can I find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it.</p>

<p>How can I get the actual path v1,v2,…vk,v1 of the cycle?</p>

<p>After applying the standard algorithm we already did n−1 iterations and no further improvement should be possible. If we can still lower the distance to a node, a negative cycle exists.</p>

<p>let say edge (v,u) is the edge that the bellman ford algorithm faild in the n-th iteration - d(u) > d(v) + w(v,u).
so we know that v,u is part of a negative cycle but the question is how do i detect the specific cycle?</p>