Seonglae ChoProcessing relaxing infinity to exact delta (shortest path)
Does not valid when graph contains negative weight cycle
Iteration
- Extract-min X from table
- Relax all edges leaving X
- apply new distances to table
Complexity
- Whole iteration is need per vertex
- Relaxation step needs to be done per edge
when graph is unweighted graph
Proof is complicate with several lemma
