그래프에서 최단 경로를 탐색할 때 가중치의 여부에 따라 '최단 경로'의 정의가 달라진다.
만약 (1) 가중치가 없는 그래프의 경우 시작 노드부터 종료 노드까지의 최소한의 간선 개수를 의미하지만,
(2) 가중치가 있는 그래프의 경우 시작 노드부터 종료 노드까지의 최소한의 가중치 합을 지닌 간선들을 의미한다.
가장 작은 가중치들의 합을 구하는 가장 유명한 두 방법은 바로 다음과 같다.
1. 다익스트라(Dijkstra) : 가장 대부분 사용하는 최단 경로 알고리즘. 하지만 음의 가중치가 있는 그래프에서는 이를 감지하지 못하며, 또한 최단 경로를 보장하지 못한다는 단점이 있다.
2. 벨만-포드(Bellman-Ford) : 주로 음의 가중치가 있는 그래프에서 사용가능한 알고리즘이다. 하지만 음의 순환을 감지할 뿐 최단 경로를 보장하지는 못한다.
1. 다익스트라 (Dijkstra)
다익스트라의 과정을 글로 쓰면 다음과 같다.
1. 시작 노드를 설정함 -> 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련함
1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값(INF)으로 초기화 함. (해당 예시에서는 무한대(Infinite)를 의미하는 INF로 표현함)
직전 노드를 저장할 공간도 INF로 초기화 함
1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 재설정
2. 해당 노드를 통해 방문할 수 있는 노드 중, 아직 방문하지 않은 노드 중에 현재까지 구한 최소 비용이 가장 적은 노드 선택
2-1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신
2-2. 이때 직전 노드도 같이 갱신
3. 노드 개수에서 1을 뺀 만큼 반복함.
글로만 보면 그 과정이 바로 이해가 되지 않을 수 있기에 그림과 함께 다익스트라 과정을 알아보자.
다음과 같은 과정을 통해 각 노드까지의 최소 비용과 직전 노드를 갱신할 수 있다.
특정 노드까지의 최적 경로를 알고싶다면, 특정 노드부터 (직전 노드가 시작 노드가 될 때까지) 직전 노드를 거슬러 올라가면 된다.
음의 가중치가 있는 그래프에서의 다익스트라는 어떨까?
결론부터 말하자면, 정확한 최단 경로를 보장하지 못한다.
바로 다익스트라 알고리즘은 그리디(탐욕)적으로 동작하기 때문이다. 자세한 이유에 대해서는 그림을 통해 알아보자.
다익스트라 알고리즘은 '당장 가장 가까운 경로'만을 보는 그리디적 알고리즘이기에
D로 갈 때 C를 거쳐서 갈 수 있다고 생각하지 못하는 것이다.
다음은 다익스트라 알고리즘과 실제 최단 경로의 비교이다.
즉, 다익스트라는 그리디적 특성 탓에 음의 가중치가 있다면 항상 정확한 최단 경로를 보장할 수 없다.
다익스트라는 음의 가중치가 없다고 확실할 수 있을 때 사용하는 것이 좋다.
그렇다면 음의 가중치가 있을 때 사용할 수 있는 최단 경로 탐색 알고리즘이 있을까?
바로 벨만-포드 알고리즘을 사용할 수 있다.
2. 벨만-포드 (Bellman-Ford)
벨만-포드의 과정을 글로 쓰면 다음과 같다.
1. 시작 노드를 설정함 : 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 설정
2. 노드 개수(N) - 1 만큼 다음 연산을 반복함
: 시작 노드에서 갈 수 있는 각 노드에 대하여,
전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인 후 있다면 갱신.
최소 비용을 갱신할 때 직전 노드 값도 같이 갱신함.
3. 마지막으로 2번 과정을 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인함.
있다면 음의 순환이 있음을 의미함.
( => 이유는 과정을 살펴본 후 알아보도록 하자. )
글로만 읽으면 헷갈리니, 그림을 통해 실제 과정이 어떻게 되는지 확인해보려고 한다.
반복 1) 먼저 시작 노드 A를 기준으로 진행한다.
1-0. 시작 노드 A 초기화
1-1. 시작 노드 A - 중간 노드 A - 도착 노드 A, B, C, D, E
1-2. 시작 노드 A - 중간 노드 B - 도착 노드 A, B, C, D, E
1-3. 시작 노드 A - 중간 노드 C - 도착 노드 A, B, C, D, E
1-4. 시작 노드 A - 중간 노드 D - 도착 노드 A, B, C, D, E
1-5. 시작 노드 A - 중간 노드 E - 도착 노드 A, B, C, D, E
♾️ 다음과 같은 과정을 똑같이 4(노드 개수 -1)번 반복한다.
반복 2) 시작 노드 B를 기준으로 진행한다.
2-0. 시작 노드 B 확인하기
2-1. 시작 노드 B - 중간 노드 D - 도착 노드 A, B, C, D, E
반복 3) 시작 노드 C를 기준으로 진행한다.
3-0. 시작 노드 C 확인하기
3-1. 시작 노드 C - 중간 노드 B - 도착 노드 A, B, C, D, E
반복 4) 시작 노드 D를 기준으로 진행한다.
4-0. 시작 노드 D 확인하기
4-1. 시작 노드 D - 중간 노드 A - 도착 노드 A, B, C, D, E
4-2. 시작 노드 D - 중간 노드 C - 도착 노드 A, B, C, D, E
반복 5) 시작 노드 E를 기준으로 진행한다.
5-0. 시작 노드 E 확인하기
5-1. 시작 노드 E - 중간 노드 C - 도착 노드 A, B, C, D, E
최종 형태는 다음과 같다. (첫 반복 1번 + 반복 4번 => 총 5번 반복)
위와 같은 과정으로 벨만-포드 알고리즘의 2번째 단계까지 수행할 수 있었다.
이제 마지막으로 3번째 단계를 수행하면, 음의 순환까지 알아볼 수 있다.
벨만-포드 알고리즘의 과정
(완료) 1. 시작 노드를 설정함 : 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 설정
(완료) 2. 노드 개수(N) - 1 만큼 다음 연산을 반복함
: 시작 노드에서 갈 수 있는 각 노드에 대하여,
전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인 후 있다면 갱신.
최소 비용을 갱신할 때 직전 노드 값도 같이 갱신함.
3. 마지막으로 2번 과정을 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인함.
있다면 음의 순환이 있음을 의미함.
( => 이유는 과정을 살펴본 후 알아보도록 하자. )
❓ 3번째 단계를 반복하는 이유는 무엇일까?
특정 노드 N의 최단 경로를 구성하는 간선 개수는 최대 N-1 이어야 한다.
즉, 최단 경로를 구성하는 간선 개수가 N개 이상일 경우 최소비용을 감소시키는 특정 간선들간의 음의 순환이 있다는 것을 나타낸다.
이와 같은 음의 순환을 발견할 수 있는 방법이 바로 3번 방법인 것이다.
만약, 음의 순환이 없는 그래프의 경우 3번을 반복한다고해도 갱신되는 최소 비용을 나타나지 않는다.
하지만 음의 순환이 있을 경우, 3번 과정을 반복할 때 갱신되는 최소 비용이 나타난다.
다익스트라와 벨만-포드의 비교
다익스트라와 벨만-포드는 출발 노드로부터 도착 노드들까지의 최단 경로를 찾는다(One To All)는 점에서는 공통점을 보인다.
그러나, 그리디 방식을 사용하는 다익스트라는 음의 가중치를 가지는 그래프에서는 최단 경로를 구할 수 없다는 것에 비해,
벨만-포드의 경우 음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있다는 차이점이 존재한다.
음의 순환을 가지는 그래프의 경우, 어떤 알고리즘을 사용해도 최단 경로를 구할 수 없지만,
벨만-포드는 음의 순환을 감지할 수는 있으므로, 음의 순환을 확신하지 못하는 상황에서 감지하기 위해 사용해볼 수 있다.