Relax every edge, V − 1 times over. Each pass extends correct shortest paths by at least one more edge, so after V − 1 passes every shortest path is found, negative edges included. One extra pass detects negative cycles.
- Average time
- O(VE)
- Space
- O(V)