[알고리즘 공부] 벨만포드 알고리즘

0. 개요

지금 진행하고 있는 코테 스터디인 알고리즘의 왕에서

정말 처음보는 알고리즘이 많이 올라와 호기심에 공부하게 되었다.

 

1. 알고리즘 개념

벨만-포드(Bellman-Ford) 알고리즘은 가중치가 있는 그래프에서

한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

 

유사한 다익스트라 알고리즘과의 차이는, 바로 음수 가중치가 있더라도 동작한다는 점이다.

또한 벨만-포드 알고리즘은 음수 사이클 존재 여부도 판별할 수 있다는 점이 또 다른 차이점이다.

 

하지만 다익스트라 알고리즘보다 성능이 낮기 때문에 정점 수가 비교적 작은 그래프에서 사용될 수 있다.

 

2. 알고리즘 구조

우선 가장 핵심적인 아이디어는 최단 경로는 최대 정점수 보다 하나 적은 수의 간선만을 포함하기 때문에,

모든 간선을 정점 수 -1 번 반복하여 검사하면 최단 거리가 완성된다는 것이다.

(사실상 모든 정점을 매번 반복해서 검사하기 때문에 성능상 느릴 수 밖에 없다)

 

더 자세하게 설명하자면,

단계를 n번 반복할 때마다, 간선을 n개를 이용해서 갈 수 있는 최단 거리를 확정할 수 있다.

예를 들어 1번 반복할 경우 현재 노드에서 간선을 1번만 이용하여 갈 수 있는 모든 노드의 최단 거리를 확정할 수 있다.

이를 정점 수 -1 번 반복하면 모든 사이클이 없는 최단 경로를 찾을 수 있다는 것이다.

 

음수 사이클을 확인할 수 있는 방법 또한 여기서 기인하는데,

만약 해당 과정을 정점 수 만큼 반복할 경우, 처음 시작한 정점으로 돌아오게 된다.

이 상황에서 비용이 저장된 정보보다 더 작아질 경우, 음수 사이클인 것을 확인할 수 있다.

 

알고리즘 동작 과정을 정리해보자면 다음과 같다.

 

1) 초기화

시작 정점의 거리를 0으로, 나머지를 무한으로 설정한다.

 

2) 간선 완화(Relaxation)

모든 간선에 대해 시작점에서 특정 정점까지 가기 위하여, 다른 정점 u를 거치는 방법이 더 싸다면 

특정 정점까지 가는 최소 비용을 정점 u를 거쳐 이동하는 비용으로 업데이트한다.

그리고 이걸 정점 수 - 1번 반복하면 최소 비용을 모두 찾을 수 있다.

 

3) 음수 사이클 검사

위의 과정을 한번 더 수행하여, 갱신이 발생하면 음수 사이클이 존재한다고 가정한다.

 

예시 코드는 다음과 같다.

struct Edge {
    int u, v, w;
};

vector<int> bellmanFord(int V, int start, vector<Edge>& edges) {
    const int INF = 1e9;
    vector<int> dist(V, INF);
    dist[start] = 0;

    // V-1번 완화
    for (int i = 0; i < V - 1; i++) {
        for (auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    // 음수 사이클 검사
    for (auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            cout << "Negative cycle detected\n";
            break;
        }
    }

    return dist;
}