[최단경로] 03. 벨만포드 알고리즘

이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자.

 

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

 

다익스트라의 한계

이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다.

 

벨만포드 알고리즘

벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.

벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거리의 상한을 미리 저장한 후 이 값을 실제 값으로 계속 맞춰가는 완탐형 알고리즘이다.

 

동작 과정

 

확실한 것은

벨만포드는 시작점에서 각 정점까지의 최단 거리의 상한을 담은 upper라는 배열을 갱신해가는 과정으로 동작한다. 이를 위해 처음 동작하면서 2가지 확실한 사실을 가정한다.

• 시작점의 상한은 당연히 0이다. 나머지 정점들은 모르기 때문에 ∞로 초기화 한다.
• 목적지(d)의 상한은 경유지(v)의 상한에 경유지(v)에서 목적지(d)까지 간선의 비용w(d-v)을 더한 것 이하이다. 정확히 같다고 하지 않은 것은 줄여가는 과정이라 아직 정확하지 않기 때문이다. 아무튼 그렇기 때문에 upper[d] = upper[v]+w(d, v)라고 할 수 있다.

 

위 내용을 이용해서 간선들을 탐색해보면 아래처럼 upper[v2]의 값을 알고 있을 때 upper[v3] = upper[v2]+w(v2,v3)가 된다. 이 중에서 특별히 출발점 s의 upper[s]=0이므로 upper[v1] = 0 + w(s, v1)이어서 v1의 상한은 확정할 수 있게 된다.

 

동작 과정

그래프가 복잡하게 있겠지만 그 중에는 최단거리가 존재할 것이고 그 최단거리 경로가 아래와 같다고 하자.

그럼 최초의 상태는 출발점 s의 상한이 0이기 때문에 다음과 같이 표현할 수 있다. 상한을 명확히 아는 지점은 테두리~~

 

이 상태에서 다익스트라는 s와 연결된 가장 가까운 정점을 갔지만 나중에 음의 간선이 나와버리면 대략 난감이었다. 따라서 벨만포드는 여기서 모든 간선들을 다 탐색해서 업데이트 가능한 정점을 업데이트 한다. 이 과정에서 최소한 upper[v1]이 확정될 것이다. 왜냐하면 가중치 간선의 정보가 주어졌고, 위 경로가 최단이라고 했고 upper[s]=0이기 때문이다.

 

그리고 다시 한번 처리하면 upper[v2] = upper[v1]+w(v1, v2)인데 v1이 확정 상태이므로 upper[v2]도 확정된다.

 

이런식으로 모든 간선을 V-1번을 돌면 마지막 정점까지 처리가 완료된다.

사실 최단 거리를 구하는데 있어서 어떤 정점을 2번 방문하면 안되니까 V-1번의 간선 연결이 필요하다는 것을 직관적으로도 알 수 있다. 

참고로 이러한 과정을 relax(완화) 라고 한다. 이러한 완화 과정을 거치면 그래프에서 발생할 수 있는 모든 경우를 다 거치게 된다. 따라서 당연히 다익스트라의 최단경로도 벨만포드에서 탐색해본 경로중 하나이다. 그리디 vs 완탐으로 시간은 훨씬 오래 걸리게 된다.

 

relax 과정

이제 음의 간선이 포함된 그래프를 구성해보자. 간선을 적용하는 순서는 우측의 순서대로 적용해볼 계획이다. 특별한 의미는 없고 relax 되는 과정이 시각적으로 보이려면 미지의 점들이 점점 발견되는게 좋기 때문이다. ㅎ

이제 모든 간선을 V-1번 돌리게 되면 벨만 포드가 완성된다.

정점	1	2	3	4	5	6	7
초기비용	0	∞	∞	∞	∞	∞	∞
1회 relax	0	min(∞, 0+2) =2	min(∞, 0+1) =1	∞	∞	∞	∞
2회 relax	0	2	min(1, 2-5) =-3	min(∞, 1+1) =2	min(∞, 1+2) =3	min(∞, 2+3) =5	∞
3회 relax	0	2	-3	min(2, -3+1) =-2	min(3,-3+2) =-1	min(5, 3+3 , 2+2, 2+3) =4	min(∞, 5+1) =6
4회 relax	0	2	-3	-2	-1	min(4, -2+2 , -1+3) =0	min(6, 4+1) =5
5회 relax	0	2	-3	-2	-1	0	min(5, 0+1) =1
6회 relax	0	2	-3	-2	-1	0	1

 

벨만포드는 다 되나?

 

음의 간선이 문제는 아니지만 음의 간선의 싸이클은..

벨만포드가 음의 간선을 고려하는 알고리즘이라고 해서 한숨 돌렸지만 모든 음의 가중치를 처리하는 것은 아니다. 아래의 경우를 살펴보자.

• 만약 1-> 2 -> 3 -> 4로 방문해본다면 총 비용은 3이다. 음이 오더라도 전혀 문제될게 없다.
• 만약 중간의 경로를 탄다면 순환이 발생해서 1-> [5 -> 6] -> 4 , 1-> [5 -> 6 -> 5 -> 6]-> 4 ,... 가 가능한데 이 순환 과정에서 비용이 12 , 15, 18 과 같이 순환이 발생할 때마다 증가하므로 최단 경로와는 상관이 없어진다. 역시 문제될 것은 없다.
• 하지만 마지막 경로를 탄다면 1-> [7 -> 8]-> 4, 1-> [7 -> 8 -> 7 -> 8]-> 4,... 로 역시 순환이 발생하는데 6, 3, 0 으로 계속 감소한다. 따라서 음으로 감소하는 싸이클을 만난다면 우리는 최단 경로를 구할 수가 없다. 벨만포드가 안되는게 아니라 최단 경로가 없다라고 해야하나..

 

음의 간선 순환 감지!

벨만포드를 조금만 응용하면 순환하는 음의 간선을 감지할 수 있다. 원래 벨만포드는 V-1번을 돌면 최단 경로가 구해지는데 반해 음의 순환 간선은 계속해서 값이 줄어들기 때문에 끝이 없다.

 

따라서 벨만포드의 동작을 V번 돌리면서 V번째에도 upper 값에 변경이 발생하면 그 그래프에 음의 순환 간선이 존재함을 알 수 있다. 

물론 음의 순환 간선이 발생했다 하더라도 세상 끝났다는 표정을 할 필요는 없다. 값이 변하지 않는 경로들은 여전히 최단 경로를 구할 수 있으니까.

 

알고리즘 구현

 

알고리즘 구현

벨만포드 알고리즘은 설명의 길이에 비해 코드는 상당히 간단한 편이다. 

일단 벨만포드는 간선 중심의 알고리즘이므로 다음과 같이 Edge 클래스를 작성해보자.

static class Edge {
    int a;
    int b;
    int w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
    @Override
    public String toString() {
        return "Edge [a=" + a + ", b=" + b + ", w=" + w + "]";
    }
}

입력을 통해 Edge의 배열을 생성했다면 다음과 같이 벨만포드의 핵심 코드를 작성할 수 있다.

static void bellmanFord(Edge [] edges) {
    long[] upper = new long[N + 1];
    // 1번 도시에서 출발한다.
    Arrays.fill(upper, Long.MAX_VALUE);
    upper[1] = 0;
    
    // 1번 더 돌았을 때 더 줄어든다면 음의 싸이클이 있다는 것
    boolean hasNegativeCycle = false;
    // 모든 정점의 개수만큼 모든 간선을 탐색
    // 원래는 정점의 개수-1 만큼 돌면 되지만 음의 cycle 판단을 위해 전체를 탐색
    for (int i = 0; i <N; i++) {
        // 모든 간선을 순회하면서 가능한 거리 업데이트
        for (int m=0; m<M; m++) {
            Edge next =edges[m]; 
            // 연결이 불가한 곳은 통과 - 그렇지 않으면 overflow 발생 가능
            if(upper[next.a]==Long.MAX_VALUE) {
                continue;
            }
            // 가능하다면 비용 갱신
            if (upper[next.b] > upper[next.a] + next.w) {
                upper[next.b] = upper[next.a] + next.w;
                // N-1번째에도 값의 변화가 발생하면 음의 cycle
                if(i==N-1) {
                    hasNegativeCycle = true;
                    break;
                }
            }
        }
        System.out.println(i+" : "+Arrays.toString(accumCost)+ " : "+hasNegativeCycle);
    }

    if (hasNegativeCycle) {
        System.out.println("음의 간선 발생");
    } else {
        System.out.println(Arrays.toString(upper);
    }
}

 

시간 복잡도

벨만포드 알고리즘의 시간 복잡도는 정점의 개수에 대한 반복 내부에 간선에 대한 반복이 이뤄지기 때문에 O(VE)로 표현할 수 있다.