Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|).

I was thinking about using Bellman-Ford to solve the question doing this: Do |V| iterations of Bellman-Ford, If there were no changes on the last iteration, there is no cycle of negative weight in the graph. Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found. This cycle will be the desired cycle of negative weight.

The problem is, that no start vertex is given, and Bellman-Ford notes wether there is reachable negative cycle via the start vertex or not. Assume that if we start from vertex a there won’t be negative cycle and if the start vertex was b there will be one. So if I choose a as a start vertex I’ll miss the negative graph.

How can I solve that? I thought about trying all the vertexes as start vertex but it won’t be O(|E|*|V|).