벨만포드1 [Algorithm] 벨만포드 알고리즘 오늘은 딕스트라 알고리즘에 이은 벨만 포드! 음수의 값이 있을 때 최단거리를 구하는 데 사용할 수 있다. 실제 상황에서 음수 거리라는 게 있을 수는 없지만... 저번 코딩 테스트 문제로 나와 당황했던 기억이 있으니 오늘 한번 풀어보려고 한다. 방식은 아래와 같다. 1. 노드 수만큼 최단거리를 표시하는 배열을 생성한다. 이 때 시작점을 제외하고는 INF 값을 넣는다. 시작점은 0을 넣어준다. 2. 노드 수 만큼 루프 하면서 모든 간선을 루핑 하는데 이때 최단거리에서 INF가 아닌 시작점이면서 도착점까지의 거리에 가중치를 더했을 때 현재의 거리보다 작아진다면 최단거리 배열을 수정한다. 3. 마지막으로 위 과정을 한번 더 적용했을 때 만약 최단거리가 또 수정된다면 이는 무한 루프에 빠진 것으로 정답이 없는 게.. 2022. 3. 25. 이전 1 다음
