Bellman-Ford Algorithm

벨만-포드 알고리즘 들어가기

그래프 알고리즘에서 최단 경로를 구하는 대표적인 알고리즘은 'Dijkstra algorithm(다익스트라 알고리즘)'이 있다. 벨만-포드 알고리즘은 다익스트라와 마찬가지로 최단 경로를 찾는 알고리즘이다. 벨만-포드 알고리즘에 대해서 먼저 알아보고, 다익스트라 알고리즘과 다른 점에 대해서 알아보도록 하자.

1. 벨만-포드 알고리즘

벨만-포드 알고리즘은 다음과 같은 과정으로 진행된다.

1. 출발 노드 선택. 모든 다른 노드까지의 거리를 무한대로 초기화. 출발 노드와 거리는 0
2. 출발 노드를 거쳐 각 노드로 가는 거리 계산. 현재까지 계산된 거리와 새로운 경로의 거리를 비교, 더 짧은 거리로 갱신.
3. 위의 과정을 모든 간선에 대해서 반복. N-1 반복 수행(N = 그래프 노드 수) 
	이를 통해서 출발 노드로부터 다른 모든 노드까지의 최단 거리 계산 가능
4. N-1의 반복 후, 모든 간선을 다시 순회하며 음의 사이클이 존재하는지 확인.
	=> 음의 사이클이 있으면 최단 거리 정의가 힘들기 떄문

이를 실제 C++ 코드로 옮겨보면 다음과 같다.

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int source, destination, weight;
};

vector<int> BellmanFord(vector<Edge>& edges, int numVertices, int source) {
    vector<int> dist(numVertices, INT_MAX); // 거리 배열을 무한대로 초기화
    dist[source] = 0; // 시작점의 거리를 0으로 설정

    // (노드 개수 - 1)번의 반복
    for (int i = 0; i < numVertices - 1; i++) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w; // 거리 갱신
            }
        }
    }

    // 음의 사이클 확인
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "음의 사이클이 존재합니다!" << endl;
            break;
        }
    }

    return dist;
}

int main() {
    // 그래프의 간선들을 정의
    vector<Edge> edges = {
        {0, 1, 6},
        {0, 2, 7},
        {1, 2, 8},
        {1, 3, -4},
        {1, 4, 5},
        {2, 3, 9},
        {2, 4, -3},
        {3, 1, 2},
        {4, 0, 3},
        {4, 3, 7}
    };

    int numVertices = 5; // 노드 개수
    int source = 0; // 시작점

    vector<int> distances = BellmanFord(edges, numVertices, source);

    // 최단 거리 출력
    for (int i = 0; i < numVertices; i++) {
        cout << "노드 " << i << "까지의 최단 거리: " << distances[i] << endl;
    }

    return 0;
}

C++을 사용하지 않는 많은 개발자들을 위해서 pseudo code도 추가하겠다.

Bellman-Ford Algorithm(Graph, start_node):
	거리 배열 dist[N] 생성. 모든 요소를 INF로 초기화
    시작점의 거리 dist[start_node] = 0으로 설정
    
    iteration(V : 노드 개수 -1):
    	iteration(모든 간선 E):
        	if dist[v] > dist[u] + weight(u,v):
            	dist[v] = dist[u] + weight(u,v)
                
    iteration(모든 간선 E):
    	if(dist[u] != INF && dist[v] > dist[u] + weight(u, v)):
        	print('음의 사이클 존재!')
            break
    
    return dist

2. 다익스트라 알고리즘과 차이

1. 가중치의 범위

   • 벨만-포드 : 음의 가중치의 간선도 처리 가능
   • 다익스트라 : 음의 가중치의 간선은 처리하기 어렵다

2. 실행 시간

   • 벨만-포드 : 모든 간선에 대해 거리 갱신, O(V * E)의 시간 복잡도
   • 다익스트라 : 우선순위 큐를 사용. O((V + E) * logV)의 시간 복잡도

3. 최적 경로 확정 시점

   • 벨만-포드 : N-1번 반복 후 최적 경로 확정
   • 다익스트라 : 각 노드까지 최단 경로 확정될 때마다 최적 경로 확정

4. 음의 사이클

   • 벨만-포드 : 음의 사이클 존재 시, 최단 경로를 정의할 수 없다고 판단한다.
   • 다익스트라 : 음의 사이클은 고려하지 않는다.

3. 음의 사이클?

음의 사이클 : 사이클의 가중치 합이 음수인 경우

이 사이클을 돌 때마다 가중치가 감소하고, 이는 음의 무한대까지 내려갈 수 있다.

벨만-포드 알고리즘은 한 정점으로부터 다른 정점까지의 최단경로는 많아야 V-1개의 간선을 지난다
는 가정으로 출발했기 때문에, 위와 같은 음의 사이클을 발견하면 최단경로가 존재하지 않는다고 판단한다.

음의 사이클이 존재하는지 확인하기 위해서 벨만-포드 알고리즘은 V-1번까지 Iteration을 돌리고, 그 이후에 더 많은 Iteration을 통해서 확인한다.

V-1개의 간선보다 더 많은 간선을 통해 최단경로를 구할 수 있다면 음의 사이클이 존재한다고 판단한다.

4. 라우팅 프로토콜

벨만-포드 알고리즘은 라우터들의 라우팅 프로토콜에 사용되는 중요한 알고리즘이다. 패킷이 네트워크에서 출발지에서 목적지로 전송될 때 어떤 경로를 따라 가야하는지 정하는 것이 라우팅 프로토콜이다. 이러한 라우팅 프로토콜 중 하나인 "Distance Vector Protocol"에서 벨만-포드 알고리즘이 사용된다.