벨만-포드 알고리즘 ( 자바 )

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

1. 단일 시작점 알고리즘 

시작점에서 다른 모든 정점까지의 최단 거리를 찾는다. 

 

 

 

2. 방향 그래프

방향 그래프를 가정으로 둔다. 

따라서, 무방향 그래프가 주어진다면 간선을 쪼개 방향 그래프로 바꿔야 한다. 

 

 

 

3 음수 가중치

음수가 아닌 가중치만 다루는 다익스트라와 다르게 음수 가중치에서도 최단 거리 문제를 정의할 수 있는 알고리즘이다. 또한, 음수 싸이클로 인해 최단 거리를 정의할 수 없는 경우도 알아낼 수 있다. 

 

 

 

 

 

동작 과정 

1 상한을 두고 최단 거리 줄여나가기

upper[i] : 정점 i까지의 최단 거리의 상한을 의미한다. 알고리즘이 진행되며 upper 오차를 줄여나간다. 최종적으로 작동이 완료되면 upper값들이 최단 거리가 된다.

 

어떻게 오차를 줄여나갈까

 

 

 

2 최단 거리 특징을 이용하여 upper 줄이기 ( relax )

두 정점 u, v가 있고, u -> v로 w가중치로 연결되어 있다. 이 때, 최단 거리[u] + w >= 최단 거리 [v]는 항상 성립한다. 왜냐하면, u를 거쳐 v로 가는 경우가 최단 거리라면 등호가 성립하고, u 말고 다른 루트가 있다면 u를 거치는 것이 더 크기 때문이다. 

 

upper에서 다음과 같은 상황을 생각해볼 수 있다. upper[u] + w < upper[v] 

이때, upper[v] = upper[u] + w로 줄일 수 있다. 왜냐하면, upper[u]는 항상 최단거리 u보다 같거나 크기 때문이다. ( upper[v]를 최단거리로 줄여야 한다. ) 이 과정을 relax라고 부른다. 

relax를 여러 번 모든 간선에서 진행하게 되면 upper[u]가 최단거리가 되며, 이어서 upper[v] 또한 최단거리가 된다. 그

 

그럼 몇 번이나 모든 간선에서 위 과정을 진행해야할까 

 

 

 

3 최대 V-1번 relax로 최단 거리 찾기

1 번 모든 간선에서 relax 진행.

upper에서 start만 0으로, 나머지는 큰 값으로 초기화 

start에서 가장 가까운 최단 거리 a가 있다면, upper[start] + weight < upper[a] 가 성립된다. 

여기서, upper[start]는 0이고 weight는 입력으로 주어지기 때문에, dist[a] = upper[a] = weight로 최단 거리를 찾을 수 있다. 

 

 

2 번 모든 간선에서 진행.

a까지의 최단 거리를 찾았으므로 한 번 더 모든 간선에서 오차를 줄이면, a 바로 다음 최단 거리의 b를 찾을 수 있다. 왜냐하면 a의 최단 거리를 이미 찾았기 때문에 b도 바로 찾을 수 있다. 

 

...

 

이와 같이, x 번 모든 간선에서 relax를 진행하면, x개 이하 간선을 거쳐야 하는 정점의 최단 거리를 알 수 있다. 

최악의 경우로, 가장 먼 간선은 V-1번 떨어져 있으므로 최대 V-1번 동작하면 모든 최단 거리를 알아낼 수 있다. 

 

+ 진행 중 relax가 하나라도 안된다면 더 이상 최단 거리를 찾을 수 없으므로 종료한다.

 

 

 

 

 

 

음수 싸이클 판정

음수 싸이클이 있다면, V번 째에도 relax가 적어도 한 번은 발생한다. 

왜냐하면, 계속해서 최단 거리를 찾아내기 때문이다. 

ex) 두 정점 u, v사이에 음수 싸이클이 존재한다고 가정하자. 그럼 u에서 v로, v에서 u로 최단 거리가 계속 줄어들게 된다. 

 

 

 

 

 

 

시간 복잡도

최대 V번 모든 간선 E를 확인하기 때문에 O(VE)

 

 

 

 

 

주의해야할 점

특정 정점까지 경로가 존재하는지 알기 위해 upper값이 초기에 설정한 max인지 아닌지로 구분하면 안 된다. 

왜냐하면, 음수 싸이클이 존재하면 최단 거리가 정의되지 않아 max 또는 다른 값으로 지정되기 때문이다. 

( 계속 최단거리를 찾아 값이 작게 변한다. )

따라서, 마지막 V번째 순회에서 음수 가중치가 없을 때만 최단 거리를 정의할 수 있다. 

 

 

 

 

구현 

upper를 Integer.MAX_VALUE 초기화 시 비교 주의

Integer.MAX_VALUE + cost >, < Integer.MAX_VALUE가 무조건 TRUE 이기 때문.

따라서, upper[u] + cost > upper[v] 를  upper[u] != Integer.MAX_VALUE 일때만 비교해야 한다. 

또한, 시작 정점에서 가장 가까운 정점부터 최솟값을 찾아가기에 문제가 없다. 

 

최단 거리 비교시, upper[u]가 초기 설정한 max값이라면 비교하지 말기 

이론적으로는 upper[u]가 무한이라면 +- 연산을 해도 무한이기 때문에 upper[v]는 그대로 무한이다.

하지만, 코드에서는 '무한'이 아니고 '큰 수'이기 때문에 의도하지 않게 값이 변할 수 있다. 

예를 들어, 시작점에서 다른 정점까지 이동가능한 것을 찾을 때, '큰 수'를 이용하여 비교한다면 잘못된 답이 된다. 

 

    
    // 최단 거리를 찾아 upper에 저장 후 true 리턴
    // 하지만, 음수 싸이클이 존재하면 false 리턴
    
    static boolean bellman_ford() {
        boolean updated = false;
        upper[1] = 0;
 
        // N 번 검사. N-1번 동안 최단 거리 생성 후 N 번째에서 음수 싸이클 검사 
        for(int cnt = 0 ; cnt < N ; cnt++) {
            updated = false;
            // 모든 간선 검사 
            for(int here = 1 ; here <= N ; here++) {
                for (node adj : adjList[here]) {
                    if( upper[here] != Integer.MAX_VALUE && upper[adj.num] > upper[here] + adj.weight) {
                        upper[adj.num] = upper[here] + adj.weight;
                        updated = true;
                    }
                }
            }
        
            if(!updated)
                break;
        }
        // N 번째에서도 update 됐다면 음수 싸이클이 존재해서 return false
        if(updated)
            return false;
        
        return true;
    }