벨만-포드란?
그래프 내의 모든 정점들 간의 최단 경로를 찾는 알고리즘 중 하나.
다익스트라 알고리즘과 유사한 작업을 수행하나, 일반적으로 다익스트라 알고리즘이 벨만포드 알고리즘과 비교하여 시간복잡도 면에서 우수합니다.
다만, 벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 작동할 수 있어서, 음의 가중치를 가진 그래프에서는 사용할 수 없는 경우에 사용됩니다.
벨만 포드 알고리즘은 시간복잡도 O(VE)를 보장하며,
전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있습니다.
벨만-포드 알고리즘의 탐색과정
노드를 중심으로 하는 다익스트라 알고리즘과는 다르게 벨만-포드 알고리즘은 에지를 중심으로 동작합니다.
그렇기 때문에,
노드를 기준으로 한 인접리스트가 아닌 에지를 기준으로 한 에지리스트를 그립니다.
이렇게 변환한 에지리스트를 바탕으로 최단 거리 배열을 생성하고 ∞를 초기값으로 설정합니다.
최단거리 배열 초기화 이후, 모든 간선을 순회하면서 최단거리 배열을 업데이트 합니다.
알고리즘의 단계는 아래와 같습니다.
- 초기화
모든 정점의 최단 거리를 무한대로 설정하고 시작 정점의 최단거리를 0으로 설정. - 반복
모든 간선을 순회하면서 최단 거리 배열을 업데이트. 이 단계는 정점(노드)의 수에서 1을 뺀 N-1만큼 반복함. - 음수 사이클 검사
위의 반복 단계를 한 번 더 실행하여 최단 거리 배열을 업데이트 한다. 만약 최단 거리 배열이 기존 값이 아니라, 새롭게 업데이트 되면 음수 사이클이 존재하는 것이다.
- 업데이트의 조건
: 최단배열[시작] != ∞ 이며, 최단배열[도착] > 최단배열[시작] + 도착 가중치- 업데이트
: 최단배열[도착] = 최단배열[시작] + 도착 가중치
위 조건식에 의거하여 매, 싸이클마다. 모든 간선을 순회하고, 이러한 싸이클을 전체 노드 수-1 만큼 반복합니다.
(간선에는 from, to, weight가 저장되어 있어, 시작과 도착. 가중치를 값으로 사용할 수 있습니다.)
(사진은 상단의 그래프에 해당하는 결과값입니다.)
이때, N-1 반복 후에. 마지막으로 한번 더 싸이클을 돌리는데,
이는 음수 싸이클의 존재 여부를 파악하기 위함입니다.
N-1만큼 반복하여, 싸이클의 완성으로 최단거리를 구하였음에도 불구하고, 재차 반복하여 최단거리 배열의 값에 변동이 있다면.
음수 싸이클이 존재하는 것이기 때문입니다.
음수 싸이클이 존재한다면, 알고리즘으로 도출한 최단거리 배열이 무의미해집니다.
무한하게 돌수록 가중치가 계속 감소하기 때문입니다.
즉, 최단거리를 구할 수 없습니다.
코드 구현
문제에 음수 가중치가 존재하기 때문에, 다익스트라 알고리즘을 사용할 수는 없습니다.
벨만포드 알고리즘을 사용하여 풀이해야합니다.
조건에 맞게 데이터를 input하여, 각 간선과 노드에 대한 값을 저장하는 그래프를 만듭니다.
이후, N,M,graph 벡터로 벨만포드 알고리즘을 구현합니다.
상단에서 설명했던, 업데이트 조건에 의거하여 조건문과 업데이트 식을 구현합니다.
if (distance[start] != LONG_MAX && distance[end] > distance[start] + time)
distance[end] = distance[start] + time;여기서 distance 벡터는 최단거리 배열이며,
LONG_MAX는 무한대 값입니다.
무한대 값이 아닐 경우, 그리고 최단거리 배열의 도착 노드값이 시작 노드값 + 가중치보다 클 경우, 배열을 갱신합니다.
N-1만큼 싸이클 반복 후.
추가 싸이클을 돌려서, 음수 싸이클이 존재하는지 파악하고, 없다면, 각 노드의 최단거리를 출력합니다.
