본문 바로가기
알고리즘/그래프와 트리

벨만-포드 알고리즘

by mozzi329 2022. 10. 13.
728x90

📌 벨만-포드 알고리즘

벨만-포드(Bellman-Ford) 알고리즘은 그래프가 가중치를 가지는 방향있는 변(Edge)으로 이루어져 있을때 한 점(Vertex)에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘이다. 

목표만 봤을 때 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 그러면 뭐가 다르냐? 바로 음의 가중치에 대해서도 최단 경로를 구할 수 있다.

 

앞서 다익스트라 알고리즘을 설명할 때 양의 가중치에서만 해당 알고리즘을 사용한다고 했었는데, 음의 가중치에서 다익스트라 알고리즘을 사용할 수 없는 이유는 다음과 같다.

 

음의 가중치 무한 순환

다음과 같은 노드가 있을 때 4번 노드로 가는 최단 경로는 1 -> 2 -> 3 -> 4이 될 것이다.

그런데 다익스트라 알고리즘 특성상 가장 작은 비용이 드는 경로를 찾기 때문에 음의 가중치인 2 -> 3 경로에서 다시, 3 -> 2로 가게되어 -2가 계속 가중되는 무한 순환이 반복되고 만다. 때문에 기존 다익스트라 알고리즘으로는 음의 가중치 문제를 풀 수 없다.

 

그래서,

기존의 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해 문제를 풀 수 있다. 다만, 시간 복잡도는 조금 올라간다.

 

다만,

음의 무한 순환에 대해 최단 경로를 찾을 수 있는 알고리즘은 아니다.

해당 알고리즘을 활용하는 것은 "벨만-포드 알고리즘을 통해 음의 무한 순환 발생을 감지할 수 있다" 라고 생각하면 된다. 물론 음의 무한 순환이 없을 경우 해당 알고리즘을 통해 최단 경로를 구할 수 있다.

 

벨먼-포드 알고리즘은 방향이 존재하는 유향 그래프(노빠꾸 그래프)에서만 사용이 가능하다. 그래서 거쳐간 노드는 다시 방문하지 않는다.

 

다익스트라와 벨만 포드 알고리즘의 차이점

  다익스트라 알고리즘 벨만-포드 알고리즘
음의 가중치 X O
음의 사이클 X X
시간 복잡도 최대 O(ElogV) 최대 O(E * V)

E는 간선의 갯수, V는 정점의 갯수이다.

 

📌 구현 과정

초기 설정

1. 정점에 대한 노드 클래스를 구현한다.

public static class Node {
    public int curIdx; // 현재 노드 위치
    public int nextIdx // 다음 노드 위치
    public int distance; // 비용
 
    public Node(int curIdx, int nextIdx, int distance) {
        this.curIdx = curIdx;
        this.nextIdx = nextIdx;
        this.distance = distance;
    }
}

 

2. 최소 비용 배열을 INF 값으로 한 번 초기화해준다.

    static int INF = Integer.MAX_VALUE;
    static long[] dist;
    
    ...
    ...
    
    dist = new long[N + 1];
    Arrays.fill(dist, INF);
    dist[start] = 0;

거기에 시작되는 노드의 최소비용을 0으로 초기화해준다.

 

 

노드 탐색 과정

먼저 N(정점의 갯수) *  M(간선의 갯수)만큼 반복문을 실행해준다.

// N * M 만큼 반복
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        Node curNode = graph.get(j);

 

해당 간선이 음의 간선인지 어떻게 알 수 있을까?

먼저는 다음 노드에서 최소 비용 값이 줄어들었는지를 확인해야 한다. 아래의 조건으로 확인해볼 수 있다. 

Node curNode = graph.get(j);
if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
    dist[curNode.nextIdx] = dist[curNode.curIdx] + curNode.distance;

dist[curNode.curIdx] != INF는 현재 노드를 방문했는지 여부를 체크한다. INF 값이 그대로 있다면 해당 위치는 방문하지 못하기 때문에 방문을 안했으므로 계속 Pass해야 한다.

 

 

음의 순환 여부 체크

if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
    ...
    ...
    // 음수 순환이 존재
    if (i == N - 1) return true;
}

 

그림과 같이 음의 순환이 이루어진다면 가시적으로는 무한 반복으로 보이지만 최소 비용 배열에선 결국 음의 가중치가 계속 누적된다.

결국 모든 순환이 마쳐질 때까지(i == N - 1) if문의 조건을 만족했다면 그것은 음의 가중치가 계속 누적된다는 의미이고 이는 음의 무한 순환을 의미한다.

 

전반적인 코드의 내용인 이게 전부이다.

아래는 백준 Q5_11657(타임머신) 문제에 대한 풀이이다.

 

📌 전체 코드

package level27_최단_경로_.Q5_11657;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;


/*
문제) 타임머신
    N개의 도시가 있다. 
    그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 
    각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 
    시간 C가 양수가 아닌 경우가 있다. 
    C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
    1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력)
    첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 
    둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력)
    만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 
    그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 
    만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.
    시간 제한 : 1초
    메모리 제한 : 256 MB
 
*/

public class Main {
    private static class Node {
        int curIdx;
        int nextIdx;
        int distance;

        public Node(int curIdx, int nextIdx, int distance) {
            this.curIdx = curIdx;
            this.nextIdx = nextIdx;
            this.distance = distance;
        }
    }

    private static int INF = Integer.MAX_VALUE;
    private static ArrayList<Node> graph = new ArrayList<>();
    private static long[] dist;


    /*
        3 4   // 도시의 갯수 N, 버스 노선의 갯수 M
        1 2 4 // 시작 도시 a, 도착 도시 b, 거리 c
        1 3 3
        2 3 -1
        3 1 -2
    */

    public static void main(String[] args) throws IOException{
        int N = readInt();
        int M = readInt();
        
        dist = new long[N + 1];

        // 노드 입력
        for (int i = 0; i < M; i++) {
            int a = readInt();
            int b = readInt();
            int c = readInt();
            
            graph.add(new Node(a, b, c));
        }

        boolean negative_cycle = bellmanFord(1, N, M);

        if (negative_cycle) {
            System.out.println(-1);
        } else {
            for (int i = 2; i <= N; i++) {
                if (dist[i] == INF) System.out.println(-1);
                else System.out.println(dist[i]);
            }
        }
    }

    private static boolean bellmanFord(int start, int N, int M) {
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // N * M 만큼 반복
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Node curNode = graph.get(j);
                if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
                    dist[curNode.nextIdx] = dist[curNode.curIdx] + curNode.distance;

                    // 음수 순환이 존재
                    if (i == N - 1) return true;
                }
            }
        }

        return false;
    }


    private static int readInt() throws IOException {
        boolean isNegative = false;
        int value = 0;
        while (true) {
            int input = System.in.read();
            if (input == '\n' || input == ' ') {
                return (isNegative) ? -1 * value : value;
            } else if (input == '-') isNegative = true;
            else value = value * 10 + (input - 48);
        }

    }
}

 

📌 참고

다익스트라 알고리즘

Q5_11657(타임머신)

댓글