벨만포드 알고리즘 수정
ganghe74 opened this issue · 2 comments
ganghe74 commented
https://www.acmicpc.net/board/view/48578
현재 코드는 오버플로우에 매우 취약하다.
ganghe74 commented
현재 코드는 전체 간선을 입력순서대로 N번 순회하면서 거리를 갱신한다.
만약 간선데이터가
1 2 -10000
2 1 -10000
1 2 -10000
2 1 -10000
...
이런식으로 주어진다면 루프를 1회 돌때마다 -10000의 거리 갱신이 아주 많이되면서 오버플로우가 날수있다.
(1) 음의 무한대에 대한 예외처리나,
(2) 간선의 입력순서대로 갱신하는게 아니라 정점 순서대로 바꾸면 될듯하다.
심지어 종만북 코드조차 위의 데이터로 저격이 가능하다