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

벨만-포드 알고리즘

벨만-포드 알고리즘
    한 정점에서 다른 모든 정점간의 최단 거리를 구하는 알고리즘이다.

    특징
    • 음의 간선을 포함하는 그래프에서 사용한다.
    • 음의 사이클의 존재여부를 판단할 수 있다.

    시간 복잡도
    • O(VE)  -  V : 정점의 개수 E : 간선의 개수

 

주요 아이디어

노드의 수가 N개일 때 N-1번 동안 모든 Edge를 탐색하면서 최단 경로를 구한다.

그러므로 시간 복잡도가 O(VE)이다.

 

아무리 멀리 떨어진 노드라고 할지라도 N-1개의 간선을 지나면 어떠한 노드라도 도달할 수 있다. 그래서 벨만 포드 알고리즘은 보통 N-1번만큼 반복하여 최단경로를 알아낸다. 

 

또한 벨만 포드 알고리즘은 주로 음의 사이클 존재 여부를 판단할 때 더 많이 쓰인다. 이때는 N번만큼 반복하며 N번일 때 최단 경로가 업그레이드 되는지 확인한다. N-1번 동안까지는 최단 경로가 업그레이드 될 수 있지만, 만약 N번의 경우에서 최단 경로가 업그레이드 된다는 것은 음의 사이클이 존재한다는 의미이다. 

 

다익스트라 알고리즘과 다른 점

한 정점에서 다른 모든 정점까지 구하는 알고리즘에는 다익스트라(Dijkstra) 알고리즘이 있다. 다익스트라 알고리즘은 음의 간선이 존재하는 그래프에서는 사용할 수 없다. 언제나 최단 거리를 구하지 못하기 때문이다. 그리디 기법으로 그 순간 최선의 선택을 하기 때문에, 한 번 방문한 노드에서는 다시 방문하지 않는다. 하지만 방문한 후에 해당 노드와 연결된 음의 간선이 나온다면 최단 경로를 더 짧아져야 하지만 이미 방문했기 때문에 갱신하지 않는 문제가 있다.

 

그리고 다익스트라 알고리즘은 벨만 포드 알고리즘보다 더 빠르다. 다익스트라 알고리즘은 현재 노드에서 연결된 노드만은 확인하지만, 벨만 포드 알고리즘은 매 번 모든 간선을 다 확인하기 때문이다. O(ElongV) < O(VE)

 

적용한 문제

해당 문제를 벨만-포드 알고리즘으로 풀어봤다.

11657번: 타임머신

 

벨만 포드 구현

벨만 포드 알고리즘

 public static long[] bellman_ford(int N, int start, ArrayList<Edge> edges){
        // start부터 각 노드까지의 최단거리를 담을 배열 생성
        long[] result = new long[N+1];
        // 중요 : 가장 큰 수(무한대)로 초기화
        Arrays.fill(result, Long.MAX_VALUE);

        // start 노드의 최단거리는 0
        result[start] = 0;

        // 반복 횟수를 N-1번으로 설정.
        // 제일 멀리 떨어진 노드들도 N-1개의 간선으로 무조건 갈 수 있기 때문
        for(int i=1; i<= N; i++){
            for(Edge edge : edges){
                // 한 번도 방문하지 않은 노드로는 최단거리를 찾을 수 없음
                if(result[edge.start] == Long.MAX_VALUE)
                    continue;
                // 루프가 반복될 수록 각 노드의 경로 값이 작은 쪽으로 바뀜
                // 연결된 노드들도 작아질 가능성이 생기므로 확인 후 작아지면 갱신
                if(result[edge.end] > result[edge.start] + edge.weight){
                    // N-1번으로 모든 간선을 갈 수있는데 N번 째에서 업그레이드가 된다는 것은
                    // 음수 사이클이 존재한다는 뜻
                    if(i == N){
                        // 음수 사이클 발생
                        return new long[]{-1};
                    }
                    result[edge.end] = result[edge.start] + edge.weight;
                }
            }
        }
        return result;

    }