Relax every edge, V - 1 times over: shortest paths even with negative weights, and a check that finds negative cycles.
This interactive visualization needs JavaScript.