다익스트라 알고리즘

정의

Dynamic Programming을 활용한 대표적인 최단 경로 탐색 알고리즘이다.
Dynamic Programming은 작은 문제가 큰 문제의 부분집합에 속해 있을 때
정리하면 작은 문제에서부터 최적의 방법을 선택해서 큰 문제까지 도달하는 것이다.

최단거리 = 여러개의 최단거리의 합

(단, 음의 거리는 포함할 수 없다.)

접근

예를 들어 1에서 각각 노드까지 가는 최단 경로를 구하고자 한다면

먼저 1과 연결된 2와 3을 봅니다.

2까지는 가는 거리는 12
3까지 가는 거리는 4 입니다.

그렇다면 여기서 최단거리가 확실한 것은 3의 거리 4입니다.
2를 통해서 3을 도착한다고 해도 결국 2의 거리인 12를 지날텐데 당연히 4보다 작을 수가 없습니다. 따라서 확실한 최단 거리는 3의 최단 거리 4입니다.

그러면 1에서 2까지 가는 방법 중에서 1-2이렇게 바로 가는 방법은 최적이 아닐 수도 있습니다.
따라서 후에 최적의 거리가 등장한다면 이 값과 비교하는 연산이 필요합니다. 또한 다익스트라는 최단의 거리에서 계속 최단 거리를 더해나가는 것이기 때문에 저렇게 배열에 모든 값에 가장 큰 값을 저장해서 저 배열 중 가장 작은 값에서 시작할 수 있도록 해야 합니다. (아래 그림의 M은 Integer.MAX_VALUE를 의미합니다.)

다익스트라는 작은 최적이 모여 큰 최적이 된다는 것이기 때문에 이제 최적인 3에서 시작합니다.

3과 연결된 4를 봅니다.
1에서 4까지 가는 최적의 방법은 1-3-4이기 때문에
1에서 4까지 가는 최적의 거리는 9입니다.

1과 3번 인덱스의 값을 제외한 4번 인덱스의 값이 최소이기 때문에 여기가 최적의 거리입니다.

이제 4부터 시작합니다.
4와 연결된 2번과 5번 노드를 봅니다.
1-3-4-2의 거리는 11
1-3-4-5의 거리는 14입니다.
따라서 기존에 있었던 2번까지의 거리는 12에서 11로 바뀝니다.

이 상황에서 최단거리는 1-3-4-2입니다.
여기서 다른 노드까지의 최단거리를 만들 수 있는지 살펴보니다.

2와 연결된 노드는 5와 1입니다.
하지만 2에서 다시 1을 가지 않기 때문에 이 경우는 빼고
5로 가는 거리는 16이기 때문에 기존의 5까지의 거리인 14보다 크기 때문에 최단거리가 아닙니다.

이렇게 해서 1에서부터의 각각 노드에 대한 최단거리가 구해졌습니다.

1에서 6으로 갈 수 있는 방법은 존재하지 않습니다.

자바 코드

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

class Main{

    static int[] answer;
    static ArrayList<ArrayList<Cost>> list;
    static class Cost{
        int x;
        int cost;
        public Cost(int x, int cost){
            this.x=x;
            this.cost = cost;
        }
    }

    static void BFS(int start){
        PriorityQueue<Cost> Q = new PriorityQueue<>((x1,x2)->{
            return x1.cost -x2.cost;
        });
        Q.offer(new Cost(1,0));
        answer[1]=0;
        while(!Q.isEmpty()){
            Cost min_starter = Q.poll();
            //이미 누군가에 의해서 최소값이 넣어졌지만 안에 중복의 vertex가 담겨져 있어서
            // 마지막에 꺼낸 경우
            if(min_starter.cost>answer[min_starter.x]) continue;
            for(Cost v : list.get(min_starter.x)){
                if(answer[v.x]>v.cost+min_starter.cost) {
                    answer[v.x] = v.cost + min_starter.cost;
                    Q.offer(new Cost(v.x,v.cost+min_starter.cost));
                }
            }
        }

    }

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        answer = new int[N+1];
        Arrays.fill(answer,Integer.MAX_VALUE);

        list = new ArrayList<>();
        for(int i=0;i<=N;i++){
            list.add(new ArrayList<Cost>());
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            list.get(start).add(new Cost(end, cost));
        }

        BFS(1);
        for(int x =2;x<=N;x++){
            if (answer[x]== Integer.MAX_VALUE){
                bw.write(Integer.toString(x)+": impossible");
            }else bw.write(Integer.toString(x)+": "+Integer.toString(answer[x]));
            bw.write("\n");
        }

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

    }


}