Finding negative cycle using Bellman Ford
Choosing a arbitrary vertex as source may not reach the negative cycle in the graph.

Assuming the graph is directed. The cycle may not be visited if there are vertices that the source node cannot reach, such as: (assuming $V_0$ is the source)


Graph containing different components or


There are vertices behind the source vertex.




So, the solution is to:


Set Dist[v]=0 for all v that has 0 in-degree (or alternatively, add an additional vertex as source, which connects to all other vertices with 0-weighted edges. (similar to Johnson's algorithm))
Run Bellman-Ford for V-1 iterations
Perform an additional iteration for marking negative paths (by ancestor backtracking)
Maintaining the minimum cycle while perform a BFS starting from the 0-in-degree vertices.