<stdio.han>

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

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

[작동방식]

1. 출발 노드를 설정한다

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

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

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

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

[예시]

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

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

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

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

총 3번 반복한다.

1번째 반복

1번 노드기준 탐색

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

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

2번 노드 기준 탐색

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

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

3번 노드 기준  탐색

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

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

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

2번째 반복

3번째 반복

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

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;
    }
}

다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐

우선순위 큐 구현에는 전 게시물에서 사용한 인정 행렬 구현을 수정해 사용한다.

https://stdio-han.tistory.com/85

[설명]

이전에 사용한 인접행렬 방식과 다른 부분을 위주로 설명한다.

// (a,b) -> a[0] - b[0] 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

먼저 우선순위 큐를 선언해준다.

  // 시작노드값 초기화
        Dist[v] = 0;
        Check[v] = true;
        pq.add(new int[]{v, 0});

시작 노드값 초기화시 우선순위 큐 pq에 시작노드와 가중치를 선언해준다.

        // 인접한 노드 Dist 갱신
        for (int i = 0; i < N; i++) {
            if (!Check[i] && Graph[v][i] != INF) { // 방문하지 않은 노드 && INF 가 아닌경우
                Dist[i] = Graph[v][i]; //값 갱신
                pq.add(new int[]{Graph[v][i], i});
            }
        }

인접한 노드에 대한 정보도 큐에 입력해준다.

while (!pq.isEmpty()) {
            // 노드 최소값 찾기
            int[] curr = pq.poll();
            int min_index = curr[1];

            // 다른 노드를 거쳐 가는 것이 더 비용이 적은지 확인
            Check[min_index] = true; // 방문한 노드 true
            for (int j = 0; j < N; j++) {
                if (!Check[j] && Graph[min_index][j] != INF) {
                    if (Dist[min_index] + Graph[min_index][j] < Dist[j]) {
                        Dist[j] = Dist[min_index] + Graph[min_index][j];
                        pq.add(new int[]{Dist[j], j});
                    }
                }
            }

            // 결과값 출력
            for (int j = 0; j < N; j++) {
                if(Dist[j] == INF) System.out.print("INF" + "\t");
                else System.out.print(Dist[j]+"\t");
            }
            System.out.println("");

        }

최소 노드값을 찾을 때 우선순위 큐에서 꺼낸다.

min_index = curr[1] 로 선언해준다. 이때 curr[0] 은 노드의 가중치, curr[1] 은 노드번호이다.

[코드]

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

public class Main {

    static int INF = Integer.MAX_VALUE;
    static int N, E; // 노드의 개수, 간선의 개수
    static int[][] Graph; // 노드들간의 가중치를 저장할 변수
    static int[] Dist; // 최단 거리를 저장할 변수
    static boolean[] Check; // 해당 노드를 방문했는지 체크할 변수
    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(), " ");

        N = Integer.parseInt(st.nextToken()); // 노드의 개수
        E = Integer.parseInt(st.nextToken()); // 간선의 개수
        Graph = new int[N][N];
        Dist = new int[N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 인접행렬 모든 값 INF 로 초기화
                Graph[i][j] = INF;
            }
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            Graph[u][v] = Graph[v][u] = cost; // 양방향 간선
        }

        dijkstra(0);

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

    public static void dijkstra(int v) {
        // (a,b) -> a[0] - b[0] 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        Dist = new int[N];
        Check = new boolean[N];

        // Dist 값 초기화
        for (int i = 0; i < N; i++) {
            Dist[i] = INF;
        }

        // 시작노드값 초기화
        Dist[v] = 0;
        Check[v] = true;
        pq.add(new int[]{v, 0});

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        // 인접한 노드 Dist 갱신
        for (int i = 0; i < N; i++) {
            if (!Check[i] && Graph[v][i] != INF) { // 방문하지 않은 노드 && INF 가 아닌경우
                Dist[i] = Graph[v][i]; //값 갱신
                pq.add(new int[]{Graph[v][i], i});
            }
        }

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        while (!pq.isEmpty()) {
            // 노드 최소값 찾기
            int[] curr = pq.poll();
            int min_index = curr[1];

            // 다른 노드를 거쳐 가는 것이 더 비용이 적은지 확인
            Check[min_index] = true; // 방문한 노드 true
            for (int j = 0; j < N; j++) {
                if (!Check[j] && Graph[min_index][j] != INF) {
                    if (Dist[min_index] + Graph[min_index][j] < Dist[j]) {
                        Dist[j] = Dist[min_index] + Graph[min_index][j];
                        pq.add(new int[]{Dist[j], j});
                    }
                }
            }

            // 결과값 출력
            for (int j = 0; j < N; j++) {
                if(Dist[j] == INF) System.out.print("INF" + "\t");
                else System.out.print(Dist[j]+"\t");
            }
            System.out.println("");

        }
    }
}

[결과]

[정리]

입력값이 커져 그래프의 크기가 커지면 커질수록 우선순위 큐가 인접행렬 방식을 사용했을때보다 시간상 이점이 발생한다.