Seonglae ChoEven with negative weight cycle
- Relaxation sequence is decided in for loop which means it can be started from arbitrary.
- Relaxation steps can be failed until both vertex is not infinity
- If not converge, which means negative-weight cycle in graph (still existing condition). After that it reports negative-weight cycle existence.
- The iteration value is because all relaxation posibility which are proven.
Proof
Shortest path must be a simple path which does not has cycle. And biggest simple path length si . That is whey iteration is enough to find all shortest path.
