[알고리즘] 벨만포드

1. 개념

그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다.

 

2. 특징

• 음수 가중치 에지가 있어도 수행할 수 있다
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다
• 시간 복잡도가 O(VE)이다. V는 노드수, E는 에지수.
• 에지 리스트를 사용하는 것이 간단하다.

 

3. 원리

• 에지 리스트를 만든다
• 최단 거리 배열을 만든다
  • 출발 노드는 0으로 설정하고, 이외의 노드는 적당히 큰 값으로 설정한다.
• 에지 리스트를 순회하면서 [출발 노드로부터 해당 에지의 출발 노드까지의 거리와 해당 에지의 가중치를 더한 값]이 [해당 에지의 도착 노드까지의 거리]보다 작으면 해당 에지의 도착 노드까지의 최단 거리 배열을 [출발 노드로부터 해당 에지의 출발 노드까지의 거리와 해당 에지의 가중치를 더한 값]으로 업데이트 한다.
  • 이는 출발 노드로부터 해당 에지까지의 경로가 있을 때만 수행되면 된다.
  • 이와 같은 과정을 전체 노드의 수 - 1 만큼 반복한다. 맨 첫 반복에서는 출발 노드-출발 노드로부터 연결 되어 있는 노드까지의 거리만 업데이트가 된다. 그리고 그 다음 반복에서는 출발 노드-출발 노드로부터 연결 되어 있는 노드와 연결 되어 있는 노드까지의 거리만 업데이트 된다. 그런데, 이렇게 연결을 해 나가면서 업데이트 된다고 할 때, 출발 노드로부터 최대로 연결 될 수 있는 횟수는 총 노드 개수 - 1 번이다. 예를 들어 모든 노드가 일직선으로 쭉 연결되어 있는 모습을 생각해보면 된다. 
• 음수 사이클 유무를 확인해서 만약 음수 사이클이 존재하면 위에서 구한 최단 거리 배열을 버리고, 음수 사이클이 없다면 위에서 구한 최단 거리 배열을 사용할 수 있다.
  • 에지의 개수만큼 돌면서 최단 거리 배열을 다시 한 번 업데이트 해 본다. 만약 업데이트 되는 부분이 있다면 음수 사이클이 있다는 것이다.
  • 음수 사이클이 존재한다는 것은 어떤 경로에 사이클이 있는데, 그 사이클의 에지 가중치들을 다 합하면 음수라는 것이다. 이 경우, 최단 경로를 구할 때 해당 음수 사이클이 경로에 있다면 최단 경로가 순환에 빠져 최단 경로의 값이 계속 줄어드는 결과를 만들어 낼 수 있다.

 

4. 코드

public static void bellFord(){
    for(int i = 1; i<N; i++){
        for(int j = 0; j<M; j++){
            Edge edge = edges[j];
            if(distance[edge.start] != Integer.MAX_VALUE && distance[edge.end] > distance[edge.start] + edge.time){
                distance[edge.end] = distance[edge.start] + edge.time;
            }
        }
    }
}

// 음수 사이클 확인
        for(int i = 0; i<M; i++){
            Edge edge = edges[i];
            if(distance[edge.start] != Integer.MAX_VALUE && distance[edge.end] > distance[edge.start] + edge.time){
                mCycle = true;
            }
        }

 

5. 관련 문제

백준 11657

 

 

백준 1219

GitHub - Lee-Min-Jung/coding_test_practice