12918번 - 정리정돈
부동소수점 오차로 인해 residual graph 안에 음수 사이클이 만들어질 수 있습니다.
최단거리 갱신 여부를 확인할 때 dist(v) > dist(u) + cost(u, v) + 1e-9 처럼 epsilon을 넣어서 비교해줍시다.
dist(v) > dist(u) + cost(u, v) + 1e-9
댓글을 작성하려면 로그인해야 합니다.
zenith82114 3년 전 7
부동소수점 오차로 인해 residual graph 안에 음수 사이클이 만들어질 수 있습니다.
최단거리 갱신 여부를 확인할 때
dist(v) > dist(u) + cost(u, v) + 1e-9처럼 epsilon을 넣어서 비교해줍시다.