[알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?

벨만-포드 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과 동일하게 최단 거리를 찾아주는 알고리즘이지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음의 가중치가 있는 그래프에서도 사용가능하며, 음수 사이클 또한 찾아낼 수 있다는 점이 다르다. 하지만 모든 간선(E)을 확인하는 작업을 V-1번 반복하기 때문에 시간복잡도가 O(VE)로, O(ElogV)인 다익스트라 알고리즘보다 느리다는 단점이 있다.

 

알고리즘 분류는 매 순간 모든 간선을 완화하면서 최적해를 점진적으로 찾아가는 방식이기 때문에 다이나믹 프로그래밍(dynamic programming)으로 분류된다.

동작방식

예시로 사용할 그래프

1. 초기화

• 시작점에서 각 정점으로 가는 최단 거리를 저장할 배열을 생성한다. 배열은 시작점과의 거리를 0으로, 다른 정점들과의 거리는 무한대(INF)로 초기화한다. (편의상 시작점은 v1로 설정하였다.)

 

2. 간선 완화 과정을 반복

간선 완화(왼쪽), 매 반복 결과(오른쪽)

• 그래프의 모든 간선을 V-1번 반복하면서, 각 간선을 확인하고 더 짧은 경로가 있다면 그 경로로 갱신한다. 벨만-포드 알고리즘에서 이 과정을 간선 완화(Edge Relaxation)라고 부른다.
• 간선 완화는 간선 (u, v)에 대해 dist[u] + weight(u, v) < dist[v]인 경우 dist[v] 값을 갱신하는 과정으로 이루어진다. 

 

3. 음수 사이클 존재 확인

• V-1번의 반복 후에도 더 짧은 경로가 발견되는 간선이 있다면, 이는 음수 사이클(Negative Cycle)이 존재한다는 의미이다. 따라서, V번째 간선 완화 과정을 진행하여 음수 사이클이 존재하는지 확인한다.

4. 최종 결과

• 최종적으로 음수 사이클이 발견되었다면 해당 사실을 반환하고, 그렇지 않다면 각 정점으로 가는 최단 거리를 저장하고 있는 배열을 반환한다.

구현 코드

struct Edge {
    int vtx1;
    int vtx2;
    int weight;
};

int V, E;
vector<Edge> edges;

vector<int> bellmanFord(int start) {

    vector<int> shortest_dist(V, INF);
    
    // init
    shortest_dist[start] = 0; 

    // V-1번 반복하여 간선 완화 + 음수 사이클 확인
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < E; j++) {
            int vtx1 = edges[j].vtx1;
            int vtx2 = edges[j].vtx2;
            int weight = edges[j].weight;

            if (shortest_dist[vtx1] != INF && shortest_dist[vtx1] + weight < shortest_dist[vtx2]) {
                shortest_dist[vtx2] = shortest_dist[vtx1] + weight;

                // 음수 사이클이 확인된경우
                if(i == V-1) return {};
            }
        }
    }

    return shortest_dist;
}

 

최단 경로 추적하기

다익스트라 알고리즘과 동일한 방식으로 최단 경로를 추적할 수 있다. 벨만-포드 알고리즘에서 최단 경로를 추적하려면, 각 정점에 도달하기 직전의 경로 정보를 저장하면된다. 이를 위해 부모(이전) 정점을 저장하는 배열을 추가하고, 최단 경로를 구할 때 이 정보를 이용해 경로를 추적하면 된다. 코드는 아래와 같다.

struct Edge {
    int vtx1;
    int vtx2;
    int weight;
};

int V, E;
vector<Edge> edges;
vector<int> parent;

vector<int> bellmanFord(int start) {

    vector<int> shortest_dist(V, INF);
    
    // init
    shortest_dist[start] = 0; 
    fill(parent.begin(), parent.end(), -1);

    // V-1번 반복하여 간선 완화 + 음수 사이클 확인
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < E; j++) {
            int vtx1 = edges[j].vtx1;
            int vtx2 = edges[j].vtx2;
            int weight = edges[j].weight;

            if (shortest_dist[vtx1] != INF && shortest_dist[vtx1] + weight < shortest_dist[vtx2]) {
                shortest_dist[vtx2] = shortest_dist[vtx1] + weight;
                parent[vtx2] = vtx1; // 다음 정점의 부모를 현재 정점으로 설정 

                // 음수 사이클이 확인된경우
                if(i == V-1) return {};
            }
        }
    }

    return shortest_dist;
}

// 최단 경로를 추적하는 함수
void printPath(int dst, const vector<int>& parent) {
    vector<int> path;
    
    // 목적지에서 시작 노드로 역추적
    for (int v = dst; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    
    // 경로를 역순으로 만들어 올바른 순서로 반환
    reverse(path.begin(), path.end());
    
    for(int vtx : path){
    	cout << vtx << " ";
    }
    cout << '\n';
}

짚고 넘어가야 할 점

반복횟수가 V-1번인 이유(주관적 의견 포함)

벨만-포드(Bellman-Ford) 알고리즘에서 V-1번 반복하는 이유는 정점 V개가 존재할 때 최대 V-1개의 간선으로 이루어진 경로가 존재할 수 있으며, V-1개의 간선으로 이루어진 경로가 간선을 읽는 순서에 따라 V-1번째에 발견될 수 있기 때문이다. 위 그림에서 시작점을 1번 정점으로 하고 벨만-포드 알고리즘을 사용한다고 했을 때, 간선을 읽는 순서가 E1~E3일 때와 E3~E1일 경우를 가정해보자.

• E1~E3일 경우:
  • 1번째 반복
    • E1: 2번 정점으로가는 최단 경로가 갱신된다.
    • E2: 3번 정점으로가는 최단 경로가 갱신된다.
    • E3: 4번 정점으로가는 최단 경로가 갱신된다.
  • 2~3번째 반복
    • 모든 정점의 최단 경로가 갱신되지 않는다.
  • 결론: 단 한 번의 반복으로 V-1개의 간선으로 이루어진 경로를 포함한 모든 최단 경로를 구했다.
• E3~E1일 경우:
  • 1번째 반복
    • E3: 3번 정점으로가는 최단 경로가 없으므로 최단 경로가 갱신되지 않는다.
    • E2: 2번 정점으로가는 최단 경로가 없으므로 최단 경로가 갱신되지 않는다.
    • E1: 2번 정점으로가는 최단 경로가 갱신된다.
  • 2번째 반복
    • E3: 3번 정점으로가는 최단 경로가 없으므로 최단 경로가 갱신되지 않는다.
    • E2: 3번 정점으로가는 최단 경로가 갱신된다.
    • E1: 최단 경로가 갱신되지 않는다.
  • 3번째 반복
    • E3: 4번 정점으로가는 최단 경로가 갱신된다.
    • E2: 최단 경로가 갱신되지 않는다.
    • E1: 최단 경로가 갱신되지 않는다.
  • 결론: V-1번 째에 V-1개의 간선으로 이루어진 경로를 포함한 모든 최단 경로를 구했다.

이렇듯, 모든 최단 경로를 구하기 위해선 V-1번 반복해야한다. 추가로, k번째 반복했을 때 k의 의미는 "시작점에서 최소 k개의 간선을 이동한 경로들 중 최단 경로"라는 의미로 받아들일 수 있다.

참고자료

https://www.youtube.com/watch?v=Ppimbaxm8d8

https://www.scaler.in/bellmanford-algorithm/

Bellman–Ford Algorithm - Scaler Blog