[C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘

벨만-포드( Bellman-Ford ) 알고리즘의 소개

벨만-포드 알고리즘은 출발 정점으로부터, 도달이 가능한 모든 정점까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.

이 알고리즘의 장점은 음수의 가중치를 가진 순환 경로가 있는 경우, 그러한 순환 경로가 있다는 것을 판단할 수 있다는 것입니다.

 

같은 목표를 가진 다익스트라( Dijkstra ) 알고리즘은 이러한 경우, 잘못된 결과를 내고, 문제 해결에 실패합니다.

다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘

 

음수 가중치를 가진 순환 경로는 벨만-포드 알고리즘의 기본적인 설명을 마친 후 계속하겠습니다.

 

시간 복잡도

V: 정점의 수, E: 간선의 수일 때,

이 알고리즘의 시간 복잡도는 O( VE )입니다.

 

이 알고리즘의 구현

그래프가 V개의 정점을 가진 경우, 출발 정점에서 임의의 정점 간의 최단 거리를 구하려면 최대 V-1개의 간선이 있어야 됩니다.

그런데, 이 V-1개의 간선이 입력되는 순서에 따라 구해지는 최단 거리가 달라지게 됩니다.

따라서, V-1 횟수만큼, 모든 간선의 가중치를 비교해서 최단 거리를 구해야, 어떤 입력 순서에도 상관없이 최단 거리를 구할 수 있게 됩니다.

 

벨만-포드 알고리즘은 시작 시,

출발 정점의 최단 거리는 0으로 하고, 나머지 정점은 최단 거리는 ∞으로 설정합니다.

그리고, 간선을 < 시작 정점, 종료 정점, 가중치 > 쌍으로 정의합니다.

 

그러면, 시작 정점을 거쳐 종료 정점까지의 최단 거리는 

min( 기존의 종료 정점까지의 최단 거리, 시작 정점까지의 최단 거리 + 가중치 )

가 됩니다.

 

이러한 값을 출발 정점에서부터 정점까지의 최단 거리를 저장하는 배열에 저장하고, 계속되는 비교에서 더 작은 값이 구해지면 갱신합니다.

 

이 과정은 코드로 보는 것이 훨씬 이해가 빠를 것입니다.

#include <vector>
#include <tuple>
#include <limits.h>
using namespace std;

using edge = tuple<int, int, int>;  // 시작 정점, 종료 정점, 가중치

int V;       		// 정점의 개수
int minDist[V+1];	// 정점까지의 최단 거리를 저장
vector<edge> Edges;     // 간선 벡터

void bellman_ford(){

    int M = Edges.size();   // 간선 개수

    for( int i = 1; i <= V; i++){
        minDist[i] = INT_MAX;   // 초기화
    }

    minDist[1] = 0;	// 출발 정점까지의 최단 거리는 0

    for( int i = 0; i < V-1; i++){	// V-1회에 거쳐 모든 간선 계산
        
        for( int j = 0; j < M; j++){	// 매회 모든 간선을 비교
            
            const edge& eg = Edges[j];
            int s = get<0>(eg);	// 시작 정점
            int e = get<1>(eg);	// 종료 정점
            int w = get<2>(eg);	// 가중치
            
            if ( minDist[s] != INT_MAX){
                if ( minDist[e] > minDist[s] + w)
                    minDist[e] = minDist[s] + w;
            }
        }
    }
}

이 함수에서는 간선의 정보를 저장하기 위해 std::tuple 객체를 사용했습니다.

tuple 객체의 사용법에 관한 내용은 여기에서 볼 수 있습니다.

[C++] std::tuple 사용법

 

이제, 이 함수의 모든 반복을 마치면 minDist 배열에 출발 정점부터 다른 정점까지의 최단 거리가 저장됩니다.

 

음수 가중치 순환 경로

다익스트라( Dijkstra ) 알고리즘이라고 해서, 음수 가중치를 가진 간선이 있다고 해서, 항상 최단 거리를 구할 수 없는 것이 아닙니다.

 

음수 가중치를 가진 간선이 있는 그래프

 

 

위의 그래프 같은 경우, 음수를 가진 간선이 있다고 해도 당연히 최단 거리를 구할 수 있습니다.

 

다익스트라 알고리즘이 해결 못하는 것은 음수 가중치 순환 경로가 있는 그래프가 주어질 때입니다.

여기서, 음수 가중치 순환 경로는 순환 경로를 만드는 간선의 가중치의 합이 음수인 순환 경로를 말합니다.

 

음수 가중치 순환 경로가 있는 그래프

 

 

위 이미지의 순환 경로를 이루는 간선 가중치의 총합은 1+10-13 = -2입니다.

이러한 순환 경로가 있으면, 다익스트라는 문제를 해결할 수 없습니다.

 

왜냐하면, 순환 경로를 지나칠 때마다, 순환 경로에 연결되어 있는 정점까지의 최단 거리가 계속 작아지기 때문입니다.

그리고, 이 경우엔 벨만-포드 알고리즘도 마찬가지로 최단 거리를 구할 수 없습니다.

 

그러나, 벨만-포드 알고리즘은 그래프에 음수 가중치 순환 경로가 있는지를 판단할 수 있습니다.

이것은 이전 항목에서 V-1회 반복해서 했던 간선 계산을 한 번만 더 수행하는 것으로 할 수 있습니다.

 

만약, 음수 가중치 순환 경로가 있다면, 간선 계산 시, 저장해 둔 최단 거리보다 작은 거리가 반드시 발생합니다.

반대로, 그러한 순환 경로가 없다면, 기존의 최단 거리는 변경되지 않습니다.

 

이제, 위의 함수를 완성시키면 다음과 같습니다.

#include <vector>
#include <tuple>
#include <limits.h>
using namespace std;

using edge = tuple<int, int, int>;  // 시작 정점, 종료 정점, 가중치

int V;       		// 정점의 개수
int minDist[V+1];	// 정점까지의 최단 거리를 저장
vector<edge> Edges;     // 간선 벡터

bool bellman_ford(){

    int M = Edges.size();   // 간선 개수

    for( int i = 1; i <= V; i++){
        minDist[i] = INT_MAX;   // 초기화
    }

    minDist[1] = 0;	// 출발 정점까지의 최단 거리는 0

    for( int i = 0; i < V-1; i++){	// V-1회에 거쳐 모든 간선 계산
        for( int j = 0; j < M; j++){
            
            const edge& eg = Edges[j];
            int s = get<0>(eg);	// 시작 정점
            int e = get<1>(eg);	// 종료 정점
            int w = get<2>(eg);	// 가중치
            
            if ( minDist[s] != INT_MAX){
                if ( minDist[e] > minDist[s] + w)
                    minDist[e] = minDist[s] + w;
            }
        }
    }
    
    bool bExistCycle = false;

    for( int j = 0; j < M; j++){
            
        const edge& eg = Edges[j];
        int s = get<0>(eg);
        int e = get<1>(eg);
        int w = get<2>(eg);
        
        // 더 작은 최단 거리가 나타나면 음수 순환 경로가 있다는 것을 알 수 있다.
        if ( minDist[s] != INT_MAX){
            if ( minDist[e] > minDist[s] + w){
                bExistCycle = true;
                break;
            }
        }
    }

    // 음수 순환 경로가 있으면 최단 거리를 구할 수 없음
    return bExistCycle;
}

 

이 알고리즘을 사용하여 문제를 해결하는 코드를 작성하는 과정은 이글에서 볼 수 있습니다.

[백준/BOJ] 11657번: 타임머신 ( 벨만-포트 알고리즘 ) - C++ 문제 풀이