벨만-포드 알고리즘은 음의 가중치를 포함하는 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 이전에 남겼던 다익스트라 알고리즘과는 다르게 음수의 가중치가 포함된 경우에도 최단거리를 구해낼 수 있습니다.
다음 블로그에서는 벨만-포드 알고리즘이 Greedy Algorithm (그리디 알고리즘) 이 아님을 설명하기 위해 아래와 같이 짧게 정리된 정의를 적었습니다.
A greedy algorithm is any problem-solving heuristic that tries to find the local optimal solution at the time, hoping that at the end, these local optimal solutions will lead to a globally optimal solution
그리디 알고리즘이란 휴리스틱, 인간 직관을 활용한 최적의 지협적 답안이 곧 모든 경우에 적용될 때에도 답이 되는 것을 가정한 알고리즘입니다.
벨만-포드 알고리즘 풀이 과정을 제가 이해한 바로 적으면 다음과 같습니다. 주어진 노드가 모두 N개라고 가정해보겠습니다.
step 1: 단방향 또는 양방향 인접 노드를 입력
step 2: 출발점에서부터 거리를 기록하는 dp 선언하고 모든 값을 최대값으로 초기화
step 3: 출발지 dp[start_point] = 0 으로 설정
step 4: N회 Loop (N-1 길이의 MST와 Negative cycle 검사 1회)
을 이용해서도 최대값을 설정할 수 있음을 배웠습니다. 전자에서는 음수 간선이 존재해도 무한의 값이 변화하지 않아 출발지점을 지정하지 않으면 그래프 변화가 유발되지 않습니다. 따라서 웜홀 문제를 풀 때 Negative cycle을 확인하기 위해 정수 값을 가지는 INF를 따로 선언하는 것이 좋습니다. 아래는 해당 문제들의 소스코드입니다.
Leave a comment