[C++/이론] Dijkstra 알고리즘의 한계점과 Bellman-Ford 알고리즘

1. 다익스트라 알고리즘의 한계

다익스트라 알고리즘은 최단거리를 찾는 일반적인 알고리즘입니다.

그러나 그래프 간선의 가중치의 값이 음수일 경우 항상 최적해를 찾는다는 보장은 없습니다.

 

물론, 다익스트라 알고리즘이 음수 가중치가 존재한다고 해서 항상 최단거리를 찾지 못하는 것은 아닙니다. 

 

 

먼저, 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 위 그래프에서 최단거리를 찾아낼 수 없습니다.

모든 간선의 가중치가 양수일 경우 방문하지 않은 vertex 중 distance 배열의 값이 최소인 노드는 자명하게 최단거리이기 때문이죠.

 

그러나 음의 가중치 값이 그래프에 존재할 경우

미래에 더 저렴한 경로를 찾을 가능성이 존재합니다. 

 

위와 같은 그래프에서는 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단거리를 찾아낼 수 있습니다.

우선순위 큐를 사용한 다익스트라 알고리즘은 방문한 노드에 또 방문할 수 있기 때문이죠,

 

 

 

그러나 우선순위 큐 다익스트라 알고리즘은 위와 같은 그래프를 해결하지 못합니다.

 

 

이런 식의 음수 가중치 간선이 포함된 사이클이 존재한다고 했을 때

사이클 순회의 총 비용이 양수인 경우에는 우선순위 큐 다익스트라가 동작하지만

사이클 순회의 총 비용이 음수인 경우에는 우선순위 큐 다익스트라는 무한 루프에 빠집니다.

 

해당 사이클을 순회할 때마다 더 저렴한 경로를 찾기 때문이죠.

 

정리하자면 다음과 같습니다.

 

그래프에 (1) 사이클이 포함되어 있고, (2) 순환의 비용이 음수라면

우선순위 큐 다익스트라 알고리즘은 무한루프에 빠질 것이고, 최단거리를 찾지 못할 것 입니다.

 

 위와 같은 그래프에서는 다익스트라 알고리즘 자체를 사용하는게 불가합니다.

 

 

2. Bellman-Ford 알고리즘

벨만-포드 최단경로 알고리즘은 음의 간선이  포함된 상황에서도 사용할 수 있습니다.

해당 알고리즘 또한 '음수 사이클 순환 문제'에 대해서는 최적해를 찾을 수는 없지만,

그럼에도 알고리즘이 수행되는데는 문제가 없으며

알고리즘을 수행한 그래프에서 음수 간선의 사이클을 감지할 수 있습니다.

 

1) 알고리즘의 논리 과정

N개의 노드를 가진 그래프가 존재할 때,

 

(1) 출발 노드를 설정합니다.

(2) 최단 거리 테이블을 INF 로 초기화 합니다. (단, 출발 노드의 비용은 0)

(3) 다음의 과정을 N - 1 번 반복합니다.

    - 전체 간선 E개를 순회한다.

    - 각 간선에 대해 특정 노드로의 최단거리를 갱신한다.

    - 출발 노드를 v 도착 노드를 u , v -> u로의 가중치를 w라고 할 때

       노드 u로의 최단거리 dist[u] 는

      dist[u] = max(dist[u], dist[v] + w)

 

(4) 만약, 음수 간선 사이클이 발생하는지 체크하고 있다면 (3) 과정을 한 번 더 수행하여

     최단 거리 테이블이 갱신되는지 확인한다.

 

 

2) 이해를 돕기위한 동영상 자료 첨부

https://youtu.be/FtN3BYH2Zes?si=3Wz7D2nA5hxaLpwF

 

 

3) C++ 코드

#include <iostream>
#include <vector>
#define INF 999'999'999
#define NUMBER_OF_VERTEX 8
using namespace std;

struct Edge
{
int from, to, w;
};

vector<Edge> adj;

void PushEdge(int from, int to, int w)
{
adj.push_back(Edge{from, to, w});
}

int main()
{
/* 간선 연결 */
{
PushEdge(1, 2, 6);
PushEdge(1, 3, 5);
PushEdge(1, 4, 5);
PushEdge(2, 5, -1);
PushEdge(3, 5, 1);
PushEdge(3, 2, -2);
PushEdge(4, 3, -2);
PushEdge(4, 6, -1);
PushEdge(5, 7, 3);
PushEdge(6, 7, 3);
}

int dist[NUMBER_OF_VERTEX] = {};

for (int i = 0; i < NUMBER_OF_VERTEX; i++)
dist[i] = INF;

dist[1] = 0;

for (int i = 0; i < NUMBER_OF_VERTEX - 1; i++)
{
for (Edge e : adj)
dist[e.to] = min(dist[e.to], dist[e.from] + e.w);
}

for (auto it : dist)
cout << it << " ";
}

 

 

속도 면에서는 다익스트라 알고리즘보다 느립니다.

시작 복잡도는 O(n³) 입니다.