길찾기 알고리즘(3) - 벨만-포드 알고리즘

벨만-포드 알고리즘

 

벨만 포드 알고리즘은 이전에 작성한 다익스트라 알고리즘, 플로이드-와샬 알고리즘과 더불어 자주 소개되는 길찾기 알고리즘입니다. 저 두개의 알고리즘보다 아주 뛰어난 성능을 가지는 알고리즘은 아니지만 아래 표와 같이 특징에 따라 분류된 알고리즘이라고 볼 수 있습니다.

 

다익스트라	플로이드-와샬	벨만-포드
빠르다 한 노드에서 다른 노드들 까지 거리를 구함 음의 가중치가 있으면 도달 불가	느리다 모든 노드 to 모든 노드의 거리를 구함 사건의 전후관계 파악에도 사용	다익스트라보다 느리다 음의 가중치가 있을때 사이클을 판단

 

 벨만-포드 알고리즘을 배우는 큰 이유는 '음의 가중치'를 판별해내기 위함입니다. 만약 A->B->C->A의 경로를 지나면 음수의 가중치가 얻어진다고 하면, 기존 알고리즘은 이 경로가 이득이기 때문에 계속해서 이곳을 맴돌게 됩니다. 이로 인해 원하는 목표지점에 도달을 할 수 없는데 다른 알고리즘은 이를 판별할 수 없다는 특징이 있습니다.

 

 벨만-포드의 경우 다른 알고리즘과는 다르게 음의 가중치로 인한 사이클의 유무를 판단하기 때문에 위 같은 경우에서 도달할 수 없는 경우 도달할 수 없다는 false값을 리턴할 수 있습니다. 따라서 다익스트라보다 살짝 느려도 이 알고리즘을 사용하게 되는 것이죠.

 

 

벨만-포드 알고리즘은 어떻게 사이클을 판단하는가?

 

 다른 알고리즘들의 경우 대부분 if문에서 기존의 경로와 비교를 한 뒤 계속해서 이득이 되는곳을 찾습니다. 하지만 벨만-포드는 '노드 to 노드'에 관점을 두기보다 경로 자체를 탐색하게 됩니다. 그래서 모든 경로를 대상으로 1번 탐색을 하고 이후 한번 더 탐색을 할 때 기존 값에서 줄어드는 값이 있다면 사이클로 판단하게 됩니다. 한마디로 보는 관점이 다르기 때문에 한번 더 돌릴 수 있는 것입니다.

 

 

 

조금 풀어쓴 벨만-포드 알고리즘

정말 간단한 예시 하나

간선 번호	1	2	3	4
출발 / 도착 / 비용	1 / 2 / 4	1 / 3 / 3	2 / 3 / -4	3 / 1 / -2

 처음 입력을 받으면 이렇게 간선 번호에 따라 3가지의 값을 가지게 됩니다. 이후 아래 흐름대로 알고리즘을 수행하게 됩니다.

 

 

1. 출발지를 지정해 줍니다. 위 예시의 경우 1번 지점을 출발지로 정합니다.

 * 아래 소스코드에서 node[1] = 0 으로 지정하는 작업에 해당합니다.

1	2	3
0	INF	INF

 

 

2. 비용이 INF가 아닌 지점에서 출발하는 간선들을 탐색합니다.

 위 예시의 경우 간선 1, 2번이 해당됩니다. INF가 아닌 지점의 의미하는건 아직 방문하지 않은 지점이라는 뜻입니다.

 결과로 아래와 같은 배열을 가지게 됩니다.

1	2	3
0	4	3

 

3. 또 한번 간선의 배열을 보게 됩니다. 2번과 3번 지점의 비용이 더이상 INF가 아니기 때문에 2, 3 지점이 출발인 간선도 탐색하게 됩니다. 따라서 위 간선 정보에서 모든 간선을 보게 됩니다.

1	2	3
-1	4	0

 

3번을 마지막으로 간선들을 1번만 이용해 탐색을 하게 됩니다.

 

 

4. 한번의 탐색을 완료한 후 한번 더 1번과 같은 방법을 반복하게 됩니다. 그리고 이 과정에서 1 > 2 > 3을 보는 과정에서 새 업데이트가 일어나게 됩니다!

1	2	3
-3	4	0

 여기서 1번 노드까지의 비용이 변경되었습니다. 변경이 된다는건 기존 값보다 더 빠른 경우가 있다는 것으로 이걸 통해서 사이클이 있다고 판단하게 됩니다.

 

 

 

 C++ 로 풀어쓴 벨만-포드 알고리즘

int n, m;
long long node[501];
vector<pair<pair<int, int>, int>> edge;

void Bellman(){
    // 벨만 포드 알고리즘
    node[1] = 0;
    for(int i = 1; i <= n-1; i++){
        for(int j = 0; j < edge.size(); j++){
            int from, to, cost;
            from = edge[j].first.first;
            to = edge[j].first.second;
            cost = edge[j].second;

            if(node[from] == 999999999)
                continue;
            
            if(node[to] > node[from] + cost)
                node[to] = node[from] + cost;
        }
    }
        //사이클이 있는지 확인하기
    for(int i = 0; i < edge.size(); i++){
        int from, to, cost;
        from = edge[i].first.first;
        to = edge[i].first.second;
        cost = edge[i].second;

        if(node[from] == 999999999)
                continue;
            
        if(node[to] > node[from] + cost){
            printf("-1\n");
            return;
        }   
    }
}

 코드에서 edge 배열에 각 간선의 정보들이 들어가 있습니다. 다른 길찾기 알고리즘들은 점에서 점으로 이동한다는 느낌이지만 벨만-포드의 경우 간선에서 출발, 도착 지점을 받아오게 됩니다. 이렇게 함으로서 길찾기를 1번만 시행할 수 있게 됩니다.

 이후 2번째 for문에서 한번 더 길찾기를 시행하게 되는데 이 과정에서 1번째 길찾기에서 나온 값보다 줄어드는 경우가 있다면 사이클이 있음으로 판단하게 됩니다.

 위 코드의 경우 -1 출력 후 종료를 했지만 사이클 유무에 따라 다른 방식의 처리를 주로 하게 됩니다.

 

 

벨만-포드 알고리즘을 이용한 문제들

 

1. 백준 1865

1865번: 웜홀

 

- 풀이

백준 1865 웜홀 - C++, 벨만-포드 알고리즘

2. 백준 11657

11657번: 타임머신

- 풀이

백준 11657 타임머신 - C++, 벨만포드 알고리즘