zenith82114   3년 전

부동소수점 오차로 인해 residual graph 안에 음수 사이클이 만들어질 수 있습니다.

최단거리 갱신 여부를 확인할 때 dist(v) > dist(u) + cost(u, v) + 1e-9 처럼 epsilon을 넣어서 비교해줍시다.

댓글을 작성하려면 로그인해야 합니다.