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

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

벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 알고리즘이다. 탐색을 하는 방식도 다익스트라와 유사하다. 다익스트라 알고리즘과의 차이점은

벨만 포드 알고리즘	다익스트라 알고리즘
음의 가중치가 간선에 있을때도 작동하며 음의 사이클도 감지함	음의 가중치가 간선에 있을경우 작동하지 않음
상대적으로 시간이 더 소요됨	벨만 포드의 알고리즘보다 시간이 덜 소요됨
시간복잡도는 O(VE)	시간복잡도는 O(ElogV)

 

[작동방식]

1. 출발 노드를 설정한다

2. 최단 거리 배열을 초기화한다.

3. 인접한 노드로 가는 간선을  탐색후 최단거리 배열을 갱신한다.

4. 3번과정을 (V-1)번 반복한다.

5. 음수 사이클의 존재 유무를 판별하려면 한 번 더 실행한다. 이때 최단거리 배열이 갱신된다면 음수 사이클이 존재하는것이다.

 

[예시]

https://www.acmicpc.net/problem/11657

11657번: 타임머신

문제 : 1번노드에서 각 노드(2번, 3번 노드)로 갈 수 있는 최단거리를 표시하고 음의 사이클이 존재하거나 갈 수 없다면 -1을 출력한다.

 

최단거리를 기록할 dist 배열 선언 및 초기화.

1	2	3
INF	INF	INF

노드가 3개이기 때문에 탐색하는 작업을 (V-1)번인 2번반복 후 마지막 음수 사이클 존재확인을 위해 1번 더 한다.

총 3번 반복한다.

 

1번째 반복

 

1번 노드기준 탐색

 

1번 노드 -> 2번 노드 = 1번 노드 가중치(0) + 간선의 가중치(4) = 4  <  INF

1번 노드 -> 3번 노드 = 1번 노드 가중치(0) + 간선의 가중치(3) = 3  <  INF

1	2	3
0	4	3

 

2번 노드 기준 탐색

 

2번 노드 -> 3번 노드 = 2번노드 가중치(4) + 간선의 가중치(-4) = 0  < 3번 노드의 가중치(3) 

3번 노드의 가중치를 더 적은 0으로 변경

1	2	3
0	4	0

 

3번 노드 기준  탐색

 

3번 노드 -> 1번 노드 =  3번의 가중치(0) + 간선의 가중치(-2) = -2  <  1번 노드의 가중치(0)

더 적은 가중치인 -2로 갱신

1	2	3
-2	4	0

 

이 과정을 2번 더 반복해주면 된다.

 

2번째 반복

1	2	3
-2	4	-4

 

3번째 반복

V번째 반복에서 V-1번째와의 결과와 다르다면 음의 사이클이 존재하다는 뜻이다.

1	2	3
-4	4	-8

2번 노드의 값은 변하지 않았지만 1, 3번노드는 음의 사이클이 존재하기 때문에 답 = -1

 

[전체 코드]

import java.io.*;
import java.util.*;

public class Main {

    static class Edge {
        int start, end, cost; // 시작 노드, 도착 노드, 가중치

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

    static int v, e;
    static List<Edge> edges;
    static long[] dist;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        v = Integer.parseInt(st.nextToken()); // 노드의 수
        e = Integer.parseInt(st.nextToken()); // 간선의 수

        // 리스트 선언
        edges = new ArrayList<>();

        // 가중치를 담을 배열
        dist = new long[v + 1];
        // dist 배열의 전체내용을 Long.MAX_VALUE 로 초기화
        Arrays.fill(dist, Long.MAX_VALUE);

        // edges 초기화
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            edges.add(new Edge(start, end, cost));
        }

        // 출력
        if (BellmanFord()) {
            // i = 2인 이유, 문제에서 0번노드부터가아닌 1번노드부터 존재
            // 1번노드 제외한 나머지 노드를 출력이기 때문에
            for (int i = 2; i <= v; i++) {
                // 도달하지 못하는 장소일 경우 -1
                if (dist[i] == Long.MAX_VALUE) {
                    sb.append(-1).append("\n");
                    continue;
                }
                // 도달가능할 경우 최소거리 출력
                sb.append(dist[i]).append("\n");
            }
        } else { // 음의 사이클이 존재할 경우 -1 출력
            sb.append(-1);
        }


        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean BellmanFord() {
        dist[1] = 0;

        // n-1번의 반복작업과 마지막(n번째 탐색) 확인작업을 한번에 실행
        for (int i = 1; i <= v; i++) {
            for (Edge edge : edges) {
                // 한번도 방문하지 않았다면 패스
                if (dist[edge.start] == Long.MAX_VALUE) {
                    continue;
                }
                // 버스 도착점까지의 최소거리가 (시작점 + 비용) 보다 크면 갱신
                if (dist[edge.end] > dist[edge.start] + edge.cost) {
                    dist[edge.end] = dist[edge.start] + edge.cost;

                    // n번째 작업에서 값이 변경되면 Negative Cycle(음의 사이클)이 존재한다는 뜻
                    if (i == v) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}