[Algorithm] 다익스트라(dijkstra) 알고리즘

다익스트라 알고리즘 !?

• 단일 시작점 최단 거리 알고리즘
  • 시작점에서 다른 모든 정점까지의 최단 경로의 길이를 찾는 문제.
• 방향 그래프
  • 무방향 그래프가 주어진다며 간선을 쪼개 방향 그래프로 바꿔야 한다.
• 0이상의 가중치
  • 음수 가중치가 존재해서는 안된다.
  • 전까지 계산해둔 최소가 최소라고 보장할 수 없기에.
  • 정점을 지날수록 가중치가 증가한다라는 사실을 전제하고 쓰인 알고리즘이다.
  • 음수 가중치가 있다면 전제가 무너진다.
• BFS를 기본으로 한다.
  • 시작 정점에서 가까운 순서대로 방문한다.
  • 방문한 정점은 최단 거리가 정해진다.
• Greedy Algoritm
  • 매 순간 최선의 선택을 고르는 알고리즘
  • 다익스트라는 탐욕 알고리즘을 사용한다.
  • 우선순위 큐를 이용하여 매 순간 최단 거리 정점을 선택한다.
  • 그래서 정당성 증명 시에 다른 최단 거리가 있을 수 있다는 가정의 귀류법을 사용한다.

우선순위 큐를 이용한 다익스트라

• dist 배열 (출발점에서 각 지점까지 최단거리 배열 초기는 모든 값이 INF)
• visited 배열
• 인접리스트 or 인접 행렬 등 그래프 간 가중치를 알 수 있어야 한다.

1. 우선순위큐(최소힙) 생성
2. 출발 정점 dist는 0으로 초기화
3. 큐에 출발정점 넣는다.
4. 큐가 비어있지 않다면 무한 반복
   4-1. 큐에서 하나를 꺼낸다
   4-2. 큐에서 꺼낸 정점을 방문한 적이 있다면 continue
   4-3. 방문한 적이 없다면?
   4-3-1. 꺼낸 정점과 연결된 모든 정점을 가져온다.
   4-3-2. 연결된 모든 각각의 정점을 next 노드라고 할때, 연결된 모든 정점에 대해 다음을 수행한다.
   4-3-2-1 현재 정점까지 거리+현재 정점에서 꺼낸 정점까지의 거리 < dist[next] 이면 dist[next]를 갱신한다.
   4-3-2-2 갱신했다면 큐에 next 노드를 넣는다.

class Main{
    static int n;
    static int m;
    static int start;
    static int[] dist;
    static boolean[] visited;
    static ArrayList<ArrayList<Node>> list = new ArrayList<>();

    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());


        // n , m , start input!
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());
        dist = new int[n+1];
        Arrays.fill(dist,987654321);
        visited = new boolean[n+1];
        for(int i=0;i<n+1;i++){
            list.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            int a,b,c;
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Node(b,c));

        }


        dijkstra(start);

        for(int i=1;i<=n;i++){
            System.out.println(dist[i]==987654321?"INF":dist[i]);
        }

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

    static void dijkstra(int start){
        dist[start] = 0;
        Node node = new Node(start,0);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(node);

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int to = cur.to;
            int time = cur.time;


            if(visited[to]) continue;
            else{
                visited[to] = true;
                ArrayList<Node> nextList = list.get(to);

                for(int i=0;i<nextList.size();i++){
                    Node temp = nextList.get(i);
                    if(dist[temp.to] > dist[to] + temp.time){
                        dist[temp.to] = dist[to] + temp.time;
                        pq.add(new Node(temp.to,dist[temp.to]));
                    }
                }
            }

        }
    }

    static class Node implements Comparable<Node>{
        int to,time;
        public Node(int to,int time){
            this.to = to;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            return this.time - o.time;
        }
    }

}